답안 #15235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15235 2015-07-12T04:20:55 Z tonyjjw 로봇 심판의 님 게임 (kriii3_F) C++
79 / 79
622 ms 2644 KB
#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;
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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