提交记录 11281


用户 题目 状态 得分 用时 内存 语言 代码长度
greenty noi18d. 【NOI2018】屠龙勇士 Accepted 100 527.103 ms 8632 KB C++11 2.74 KB
提交时间 评测时间
2019-11-12 20:53:15 2020-08-01 02:41:25
#include<bits/stdc++.h>
using namespace std;
#define debug
const int N = 1e5+5;
typedef long long ll;
ll read(){
	ll d=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))d=d*10+ch-'0',ch=getchar();
	return d*f;
}
// input data
int n,m;
ll HP[N],PLUS[N],ATK[N];
multiset<ll>st;
void csh(){
	st.clear();
}
void input(){
	n=read(),m=read();
	for(int i=0;i<n;i++) 
		HP[i] = read();
	for(int i=0;i<n;i++)
		PLUS[i] = read();
	for(int i=0;i<n;i++)
		ATK[i] = read();
	for(int i=1;i<=m;i++) 
		st.insert(read());
}
ll mul(ll a,ll b,ll mod){
    ll res=0;
    b=b%mod;if(b<0)b+=mod;
    while(b>0){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return (res+mod)%mod;
}
// excrt
ll exgcd(ll a,ll b,ll& x,ll& y){
    if(b==0) {
        x=1;y=0;
        return a;
    }
    ll g = exgcd(b,a%b,x,y);
    ll tmp = x;
    x=y;
    y=tmp-a/b*y;
    return g;
}
ll inv(ll a,ll p){
	ll x,y;
	exgcd(a,p,x,y);
	return (x%p+p)%p;
}
ll a[N],r[N];
ll get_aa(ll H) {
	auto it = st.begin();
	if((*it) >= H) {
		ll res = *it;
		st.erase(it);
		return res;
	}
	it = st.upper_bound(H);
	it--;
	ll res = *it;
	st.erase(it);
	return res;
}
ll solve(ll a,ll b,ll c) {
    ll x,y;
    ll d = exgcd(a,b,x,y);
    if(c%d) return -1;
    ll mod = b/d;
    x = mul(x,c/d,mod);
    return x;
}
void tp1(){
        ll ans = 0;
        for(int i=0;i<n;i++){
                ll aa = HP[i];
                ll cc = ATK[i];
                ll tmp = aa / cc;
                if(aa%cc) tmp++;
                ans = max(ans, tmp);
        }
        printf("%lld\n",ans);
}
bool init(){
	
	for(int i=0;i<n;i++){
		ll tmp = get_aa(HP[i]);
		st.insert(ATK[i]);
		ATK[i] = tmp;
	}
	
	bool flag = 0;
        for(int i=0;i<n;i++){
            if(PLUS[i]>1) {
                flag=1;
                break;
            }
        }
        if(flag == 0) {
            tp1();
            return 0;
        }
	for(int i=0;i<n;i++) {
		if(ATK[i]==0){
			if(PLUS[i] == HP[i]) {
				ATK[i] = PLUS[i] = 1;
				HP[i] = 0;
			}
			else {
				puts("-1");
				return 0;
			}
		}
	}
	for(int i=0;i<n;i++) {
		ll sx,sy;
		ll g = exgcd(ATK[i],PLUS[i],sx,sy);
		if(HP[i]%g) {
			puts("-1");
			return 0;
		}
		PLUS[i] = PLUS[i]/g;
		sx = (sx%PLUS[i]+PLUS[i])%PLUS[i];
		HP[i] = mul(sx,HP[i]/g,PLUS[i]);
		a[i] = PLUS[i];
		r[i] = HP[i];
	}
	return 1;
}

ll excrt()
{
    ll x,y;
    ll M=a[0],ans=r[0];
    for(int i=1;i<n;i++)
    {
        ll _a=M,b=a[i],c=(r[i]-ans%b+b)%b;
        ll gcd=exgcd(_a,b,x,y),bg=b/gcd;
        if(c%gcd!=0) return -1;
        x=mul(x,c/gcd,bg);
        ans+=x*M;
        M*=bg;
        ans=(ans%M+M)%M;
    }
    return ans;
}
int main(){
	int _ = read();
	while(_--) {
		csh();
		input();
		if(init() == 0) continue;
		ll x = excrt();
		printf("%lld\n",x);
	}
} 	

CompilationN/AN/ACompile OKScore: N/A

Testcase #126.157 ms2 MB + 340 KBAcceptedScore: 5

Testcase #226.015 ms2 MB + 340 KBAcceptedScore: 5

Testcase #330.1 ms2 MB + 340 KBAcceptedScore: 5

Testcase #429.863 ms2 MB + 340 KBAcceptedScore: 5

Testcase #52.417 ms148 KBAcceptedScore: 5

Testcase #62.35 ms148 KBAcceptedScore: 5

Testcase #72.402 ms148 KBAcceptedScore: 5

Testcase #841.91 us60 KBAcceptedScore: 5

Testcase #942.15 us60 KBAcceptedScore: 5

Testcase #1039.83 us60 KBAcceptedScore: 5

Testcase #1140.95 us60 KBAcceptedScore: 5

Testcase #1240.24 us60 KBAcceptedScore: 5

Testcase #1340.5 us60 KBAcceptedScore: 5

Testcase #14241.967 ms6 MB + 932 KBAcceptedScore: 5

Testcase #15242.615 ms6 MB + 932 KBAcceptedScore: 5

Testcase #16527.103 ms8 MB + 440 KBAcceptedScore: 5

Testcase #17526.693 ms8 MB + 440 KBAcceptedScore: 5

Testcase #18526.857 ms8 MB + 440 KBAcceptedScore: 5

Testcase #19520.142 ms8 MB + 440 KBAcceptedScore: 5

Testcase #20501.764 ms8 MB + 440 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 22:49:58 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用