提交记录 5163


用户 题目 状态 得分 用时 内存 语言 代码长度
noi18std noi18d. 【NOI2018】屠龙勇士 Accepted 100 585.759 ms 7836 KB C++11 2.16 KB
提交时间 评测时间
2018-08-08 21:53:08 2020-08-01 00:12:25
#include<cstdio>
#include<algorithm>
#include<set>
#define N 100000

long long read()
{
long long ret=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
	{
	ret=(ret<<3)+(ret<<1);
	ret+=c-'0';
	c=getchar();
	}
return ret;
}

long long exgcd(long long a,long long b,long long&x,long long&y)
{
	if(a<b)return exgcd(b,a,y,x);
	if(b==0)
		{
		x=1;
		y=0;
		return a;
		}
	long long d=exgcd(b,a%b,x,y);
	long long tmpx=y;
	long long tmpy=x-a/b*y;
	x=tmpx;
	y=tmpy;
	return d;
}

long long product_mod(long long a,long long b,long long mod)
{
	if(b==0)return 0;
	if(b==-1)return (-a)%mod;
	long long t=product_mod(a,b>>1,mod);
	if(b&1)
		return (t+t+a)%mod;
	return (t+t)%mod;
}

long long life[N];
long long cure[N];
long long drop[N];
long long attack[N];

int T,n,m;
std::multiset<long long>sword;
typedef std::multiset<long long>::iterator IT;

int main()
{
scanf("%d",&T);
while(T--)
	{
	scanf("%d%d",&n,&m);
	sword.clear();
	for(int i=0;i<n;++i)life[i]=read();
	for(int i=0;i<n;++i)cure[i]=read();
	for(int i=0;i<n;++i)drop[i]=read();
	for(int i=0;i<m;++i)
		{
		long long tmp=read();
		sword.insert(tmp);
		}
	for(int i=0;i<n;++i)
		{
		IT tmp=sword.lower_bound(life[i]);
		if(tmp!=sword.begin()&&*tmp!=life[i])--tmp;
		attack[i]=*tmp;
		sword.erase(tmp);
		sword.insert(drop[i]);
		}
	long long max=0;
	for(int i=0;i<n;++i)
		if(cure[i]!=1)
			{
			max=-1;
			break;
			}
		else
			max=std::max(max,(life[i]+attack[i]-1)/attack[i]);
	if(~max)
		{
		printf("%lld\n",max);
		continue;
		}
	long long ans=0;
	long long mod=1;
	long long x,y;
	bool flag=true;
	for(int i=0;i<n;++i)
		{
		long long d=exgcd(cure[i],attack[i],x,y);
		if(life[i]%d)
			{
			flag=false;
			break;
			}
		life[i]/=d;
		cure[i]/=d;
		attack[i]/=d;
		}
	for(int i=0;i<n&&flag;++i)
		{
		long long d=exgcd(attack[i]*mod,cure[i],x,y);
		if((life[i]-ans*attack[i])%d)
			{
			flag=false;
			break;
			}
		long long tmp=mod;
		long long gcd=d;
		long long tmpx=x;
		d=exgcd(mod,cure[i],x,y);
		mod=mod/d*cure[i];
		ans+=product_mod(tmp,product_mod(tmpx,(life[i]-ans*attack[i])/gcd,mod),mod);
		ans%=mod;
		}
	if(flag)
		{
		if(ans<=0)ans+=mod;
		printf("%lld\n",ans%mod);
		}
	else
		printf("-1\n");
	}
return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #124.752 ms3 MB + 76 KBAcceptedScore: 5

Testcase #224.581 ms3 MB + 76 KBAcceptedScore: 5

Testcase #329.294 ms3 MB + 76 KBAcceptedScore: 5

Testcase #429.184 ms3 MB + 76 KBAcceptedScore: 5

Testcase #52.576 ms120 KBAcceptedScore: 5

Testcase #62.683 ms120 KBAcceptedScore: 5

Testcase #72.436 ms120 KBAcceptedScore: 5

Testcase #822.05 us40 KBAcceptedScore: 5

Testcase #921.35 us40 KBAcceptedScore: 5

Testcase #1021.31 us40 KBAcceptedScore: 5

Testcase #1121.24 us40 KBAcceptedScore: 5

Testcase #1220.9 us40 KBAcceptedScore: 5

Testcase #1321.57 us40 KBAcceptedScore: 5

Testcase #14238.85 ms7 MB + 668 KBAcceptedScore: 5

Testcase #15238.805 ms7 MB + 668 KBAcceptedScore: 5

Testcase #16584.066 ms7 MB + 668 KBAcceptedScore: 5

Testcase #17585.759 ms7 MB + 668 KBAcceptedScore: 5

Testcase #18552.197 ms7 MB + 668 KBAcceptedScore: 5

Testcase #19543.154 ms7 MB + 668 KBAcceptedScore: 5

Testcase #20541.421 ms7 MB + 668 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-12-05 04:54:09 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠