Submission #15235

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15235	2015-07-12T04:20:55 Z	tonyjjw	로봇 심판의 님 게임 (kriii3_F)	C++	79 / 79	622 ms	2644 KB

S

#include<stdio.h>
int n,m,k;
int p[20];
long long int nim[25];
long long int ns[25];
long long int pp[100000];
long long int qq[100000];
long long int gcd(long long int x,long long int y){
	if(x==0)return y;
	return gcd(y%x,x);
}
long long int f(long long int x){
	long long int i,res=0;
	for(i=0;i<(1<<(n+m));i++){
		res+=(x/pp[i])*qq[i];
	}
	return res;
}
int main(){
	int i,j;
	long long int ii,jj,kk;
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++){
		scanf("%d",&p[i]);
	}
	for(i=0;i<m;i++){
		scanf("%d",&p[i+n]);
	}
	for(i=0;i<k;i++){
		scanf("%lld",&nim[i]);
		for(j=0;j<n;j++){
			if(nim[i]%p[j]==0)break;
		}
		if(j!=n)nim[i]=0;
		for(j=0;j<m;j++){
			if(nim[i]%p[n+j]==0)break;
		}
		if(j==m)nim[i]=0;
	}
	for(i=0;i<(1<<(n+m));i++){
		ii=1;
		jj=0;
		kk=0;
		for(j=0;j<n+m;j++){
			if(i&(1<<j)){
				if(j<n)jj++;
				else kk++;
				ii/=gcd(ii,p[j]);
				ii*=p[j];
			}
			if(ii>(1e12)+(1e8)){
				ii=(1e12)+(1e8);
			}
		}
		pp[i]=ii;
		for(j=0;j<k;j++){
			if(jj%2==0&&kk%2==1){
				ns[j]+=nim[j]/ii;
				qq[i]=1;
			}
			else if(jj%2==0&&kk!=0){
				ns[j]-=nim[j]/ii;
				qq[i]=-1;
			}
			if(jj%2==1&&kk%2==1){
				ns[j]-=nim[j]/ii;
				qq[i]=-1;
			}
			else if(jj%2==1&&kk!=0){
				ns[j]+=nim[j]/ii;
				qq[i]=1;
			}
		}
	}
	kk=0;
	for(i=0;i<k;i++){
		kk^=ns[i];
	}
	for(i=0;i<k;i++){
		if(ns[i]!=0&&ns[i]==kk){
			ii=-1;
			for(j=42;j>=0;j--){
				ii+=1LL<<j;
				if(ii>nim[i])ii-=1LL<<j;
				else if(ii-f(ii)==nim[i]-ns[i])ii-=1LL<<j;
			}
			ii++;
			printf("%lld %lld\n",nim[i]-ns[i]+1,nim[i]-ii);
		}
		else if(ns[i]>(ns[i]^kk)){
			ii=-1;
			for(j=42;j>=0;j--){
				ii+=1LL<<j;
				if(f(ii)>=(ns[i]^kk))ii-=1LL<<j;
			}
			ii++;
			printf("1 %lld\n",nim[i]-ii);
		}
		else{
			printf("0 0\n");
		}
	}
	
	return 0;
}

Subtask #1

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	302 ms	2644 KB	Output is correct
2	Correct	371 ms	2644 KB	Output is correct
3	Correct	457 ms	2644 KB	Output is correct
4	Correct	452 ms	2644 KB	Output is correct
5	Correct	446 ms	2644 KB	Output is correct
6	Correct	451 ms	2644 KB	Output is correct
7	Correct	364 ms	2644 KB	Output is correct
8	Correct	357 ms	2644 KB	Output is correct
9	Correct	462 ms	2644 KB	Output is correct
10	Correct	374 ms	2644 KB	Output is correct
11	Correct	119 ms	2644 KB	Output is correct
12	Correct	546 ms	2644 KB	Output is correct
13	Correct	504 ms	2644 KB	Output is correct
14	Correct	423 ms	2644 KB	Output is correct
15	Correct	468 ms	2644 KB	Output is correct
16	Correct	622 ms	2644 KB	Output is correct
17	Correct	385 ms	2644 KB	Output is correct
18	Correct	329 ms	2644 KB	Output is correct
19	Correct	409 ms	2644 KB	Output is correct
20	Correct	561 ms	2644 KB	Output is correct
21	Correct	364 ms	2644 KB	Output is correct
22	Correct	308 ms	2644 KB	Output is correct
23	Correct	325 ms	2644 KB	Output is correct
24	Correct	360 ms	2644 KB	Output is correct
25	Correct	491 ms	2644 KB	Output is correct
26	Correct	149 ms	2644 KB	Output is correct
27	Correct	607 ms	2644 KB	Output is correct
28	Correct	380 ms	2644 KB	Output is correct
29	Correct	470 ms	2644 KB	Output is correct
30	Correct	252 ms	2644 KB	Output is correct
31	Correct	0 ms	2644 KB	Output is correct
32	Correct	0 ms	2644 KB	Output is correct
33	Correct	0 ms	2644 KB	Output is correct
34	Correct	0 ms	2644 KB	Output is correct
35	Correct	0 ms	2644 KB	Output is correct

Subtask #2

51.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2644 KB	Output is correct
2	Correct	0 ms	2644 KB	Output is correct
3	Correct	28 ms	2644 KB	Output is correct
4	Correct	466 ms	2644 KB	Output is correct
5	Correct	372 ms	2644 KB	Output is correct
6	Correct	323 ms	2644 KB	Output is correct
7	Correct	491 ms	2644 KB	Output is correct
8	Correct	527 ms	2644 KB	Output is correct
9	Correct	500 ms	2644 KB	Output is correct
10	Correct	444 ms	2644 KB	Output is correct