Submission #15281

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15281	2015-07-12T05:17:16 Z	progressive	로봇 심판의 님 게임 (kriii3_F)	C++14	0 / 79	2000 ms	1084 KB

S

#include<cstdio>
#include<algorithm>
using namespace std;
inline long long lcm(long long A,long long B)
{
	return A*B/__gcd(A,B);
}
//!( n(p1|x v p2|x) - n(p1|x v p2|x v q1|x v q2|x))
int N,M,K;
int P[20],Q[20];
long long A[50];
long long cnt[50];
long long count(long long A)
{
	long long cnt=0;
	for(int i=0;i<(1<<N);i++)
	{
		long long LCM=1;
		bool overflow=false;
		int parity=0;
		for(int j=0;j<N;j++)
		{
			if(i&(1<<j))
			{
				parity++;
				LCM=lcm(LCM,P[j]);
				if(LCM>A)
				{
					overflow=true;
					break;
				}
			}
		}
		if(overflow) continue;
		if(parity%2==0) cnt+=A/LCM;
		else cnt-=A/LCM;
	}
	
	for(int i=0;i<(1<<N);i++)
	{
		for(int q=0;q<(1<<M);q++)
		{
			long long LCM=1;
			bool overflow=false;
			int parity=1;
			for(int j=0;j<N;j++)
			{
				if(i&(1<<j))
				{
					parity++;
					LCM=lcm(LCM,P[j]);
					if(LCM>A)
					{
						overflow=true;
						break;
					}
				}
			}
			if(overflow) continue;
			for(int j=0;j<M;j++)
			{
				if(q&(1<<j))
				{
					parity++;
					LCM=lcm(LCM,Q[j]);
					if(LCM>A)
					{
						overflow=true;
						break;
					}
				}
			}	
			if(overflow) continue;
			if(parity%2==0) cnt+=A/LCM;
			else cnt-=A/LCM;
		}
	}
	return cnt;
}
int main()
{
	scanf("%d%d%d",&N,&M,&K);
	for(int i=0;i<N;i++) scanf("%d",P+i);
	for(int i=0;i<M;i++) scanf("%d",Q+i);
	for(int i=0;i<K;i++)
	{
		scanf("%lld",A+i);
		cnt[i]=count(A[i]);
		//printf("%lld: %lld\n",A[i],cnt[i]);
	}
	long long grundy=0;
	for(int i=0;i<K;i++)
		grundy^=cnt[i];
	//fprintf(stderr,"%lld",grundy);
	for(int i=0;i<K;i++)
	{
		bool discard=false;
		for(int j=0;j<N;j++)
		{
			if(A[i]%P[j]==0)
				discard=true;
		}
		int dcnt=0;
		for(int k=0;k<M;k++)
		{
			if(A[i]%Q[k]==0) dcnt++;
		}
		long long grundytomake=grundy^cnt[i];
		if(discard || dcnt==0 || cnt[i]<grundytomake)
		{
			puts("0 0");
			continue;
		}
		if(grundytomake==0LL)
		{//find max cnt[i]-1
			long long lo=0; // <cnt[i]
			long long hi=A[i]; //>=cnt[i]
			while(lo+1!=hi)
			{
				long long mi=(lo+hi)/2;
				if(count(mi)<cnt[i]) lo=mi;
				else hi=mi;
			}
			printf("%lld %lld\n",A[i]-cnt[i]+1,A[i]-lo);
			continue;
		}
		else
		{//find min grundytomake
			long long lo=0;// <grundytomake
			long long hi=A[i]; //>=grundytomake
			while(lo+1!=hi)
			{
				long long mi=(lo+hi)/2;
				if(count(mi)<grundytomake) lo=mi;
				else hi=mi;
			}
			printf("%lld %lld\n",1LL,A[i]-hi);
		}
	}
	return 0;
}

Subtask #1

0.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2000 ms	1084 KB	Program timed out
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-