QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#595092#9432. Permutationucup-team3555#AC ✓303ms4412kbC++143.1kb2024-09-28 12:31:292024-09-28 12:31:42

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 12:31:42]
  • 评测
  • 测评结果:AC
  • 用时:303ms
  • 内存:4412kb
  • [2024-09-28 12:31:29]
  • 提交

answer

/*
I know this sky loves you
いずれ全て
変わってしまったって
空は青いだろうよ
*/

# include <bits/stdc++.h>

const int N=100010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int n;
std::mt19937 rng(0);
int p[N];

typedef std::vector <int> vec;

vec ban;

inline int query(vec arr){
	printf("0 ");
	for(auto v:arr) printf("%d ",v);
	puts("");
	fflush(stdout);
	return read();
}

inline void guess(vec arr){
	printf("1 ");
	for(auto v:arr) printf("%d ",v);
	puts("");
	fflush(stdout);
	return;
}

bool loc[N];

vec rem;
vec ans;

inline void get_pos(void){
	vec().swap(rem);
	for(int i=0;i<n;++i) if(!loc[i]) rem.push_back(i);
	return;
}

inline void double_query(int lu,int ru,int lv,int rv,vec pos,int u,int v){
//	printf("double_query lu = %d ru = %d lv = %d rv = %d u = %d v = %d\n",lu,ru,lv,rv,u,v);
	
	if(lu==ru&&lv==rv)
		return ans[pos[lu]]=u,ans[pos[lv]]=v,loc[pos[lu]]=loc[pos[lv]]=true,void();
	
	int midu=(lu+ru)>>1;
	int midv=(lv+rv)>>1;
	
	vec arr=ban;
	
	std::vector <int> lp,rp;
	
	for(int i=lu;i<=midu;++i) arr[pos[i]]=u,lp.push_back(i);
	for(int i=midu+1;i<=ru;++i) rp.push_back(i);
	for(int i=lv;i<=midv;++i) arr[pos[i]]=v,lp.push_back(i);
	for(int i=midv+1;i<=rv;++i) rp.push_back(i);
	
	int ret=query(arr);
	
	if(ret==2){
		return double_query(lu,midu,lv,midv,pos,u,v);
	}else if(ret==0) return double_query(midu+1,ru,midv+1,rv,pos,u,v);
	
	arr=ban,vec().swap(lp),vec().swap(rp);

	for(int i=lu;i<=midu;++i) rp.push_back(i);
	for(int i=midu+1;i<=ru;++i) arr[pos[i]]=u,lp.push_back(i);
	for(int i=lv;i<=midv;++i) arr[pos[i]]=v,lp.push_back(i);
	for(int i=midv+1;i<=rv;++i) rp.push_back(i);

	ret=query(arr);
	if(ret==2) return double_query(midu+1,ru,lv,midv,pos,u,v);
	return double_query(lu,midu,midv+1,rv,pos,u,v);
}

inline void query(vec pos,int u,int v){
	int len=pos.size();
	
//	printf("u = %d v = %d\n",u,v);
//	for(auto v:pos) printf("remain: %d",v); puts("");
	
	vec arr=ban;
	for(int i=0;i<len/2;++i) arr[pos[i]]=u;
	for(int i=len/2;i<len;++i) arr[pos[i]]=v;
	int ret=query(arr);
	if(ret==2||ret==0){
		if(ret==0) std::swap(u,v);
		return double_query(0,len/2-1,len/2,len-1,pos,u,v);
	}else{
		for(int i=0;i<len/2;++i) arr[pos[i]]=ban[pos[i]];
		int nw=query(arr);
		vec np;
		if(nw==1) for(int i=len/2;i<len;++i) np.push_back(pos[i]);
		else for(int i=0;i<len/2;++i) np.push_back(pos[i]);
		return query(np,u,v);
	}
	assert(0);
	return;
}

int main(void){
	n=read(); ans=vec(n,0);
	
	if(n==1) guess(vec(1,1)),exit(0);
	
	vec arr;
	arr.resize(n); std::iota(arr.begin(),arr.end(),1);
	
	do{
		std::shuffle(arr.begin(),arr.end(),rng);
	}while(query(arr)!=0);
	
//	printf("yes!\n");
//	puts("correct"); return 0;
	
	ban=arr;
	
	vec val(n); std::iota(val.begin(),val.end(),1);
	
	std::shuffle(val.begin(),val.end(),rng);
	
	for(int i=0;i<n;i+=2){
		get_pos();
		
		if(i==n-1) ans[rem[0]]=val[i];
		else{
			query(rem,val[i],val[i+1]);
		}
	}
	guess(ans);

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3752kb

input:

5
2
2
1
1
3
0
0
0
2
1
0

output:

0 3 5 4 1 2 
0 3 2 5 1 4 
0 5 2 4 1 3 
0 4 3 5 1 2 
0 3 4 2 5 1 
0 2 5 1 4 3 
0 5 5 4 4 4 
0 4 5 5 5 3 
0 3 5 1 1 3 
0 3 5 1 4 3 
0 2 5 1 4 3 
1 3 4 2 1 5 

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 280ms
memory: 4096kb

input:

1000
3
2
1
1
3
1
0
0
2
2
1
2
2
0
2
1
0
0
1
0
1
1
2
1
0
0
2
0
2
1
2
1
0
0
1
1
1
1
1
1
2
2
0
0
1
0
0
1
0
2
2
0
1
2
1
2
1
0
0
1
2
1
2
0
2
1
2
2
2
0
2
0
0
0
1
0
1
0
1
0
1
1
1
0
1
1
2
0
0
1
2
1
0
1
0
2
1
0
0
1
2
0
1
2
1
0
1
0
2
1
1
2
2
2
1
2
2
1
2
0
1
0
2
1
1
2
1
2
1
2
1
0
1
0
1
0
2
1
2
1
2
2
1
0
1
0
1
2...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 992 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #3:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

2
0
0

output:

0 1 2 
0 1 2 
1 2 1 

result:

ok Accepted

Test #5:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

3
1
0
0
2

output:

0 3 2 1 
0 1 2 3 
0 1 3 3 
0 3 1 3 
1 3 1 2 

result:

ok Accepted

Test #6:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

4
1
0
1
1
0
0

output:

0 1 3 2 4 
0 1 3 4 2 
0 1 1 2 2 
0 1 3 2 2 
0 1 3 1 2 
0 4 3 4 2 
1 3 4 2 1 

result:

ok Accepted

Test #7:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

6
2
0
0
1
2
1
0
0
1
0
2

output:

0 1 3 2 6 4 5 
0 1 5 3 6 4 2 
0 6 6 6 2 2 2 
0 2 2 3 6 6 2 
0 1 5 2 6 6 2 
0 1 5 2 6 4 2 
0 1 5 3 6 4 2 
0 5 5 3 3 4 3 
0 3 5 3 5 4 2 
0 1 3 3 5 4 2 
0 1 4 3 1 4 2 
1 3 4 2 1 6 5 

result:

ok Accepted

Test #8:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

7
4
1
1
0
1
1
1
1
2
2
1
2
1
0
1
1
2

output:

0 3 5 7 1 6 2 4 
0 3 4 6 7 1 2 5 
0 6 1 2 5 4 3 7 
0 2 1 7 6 5 4 3 
0 5 5 5 4 4 4 4 
0 2 1 7 4 4 4 4 
0 2 1 7 5 5 4 4 
0 2 1 7 6 5 4 4 
0 2 1 7 6 5 5 4 
0 7 7 1 1 1 4 3 
0 7 1 1 1 5 4 3 
0 2 7 1 1 5 4 3 
0 2 7 1 6 5 4 3 
0 2 1 1 6 5 4 3 
0 2 1 6 6 6 4 3 
0 2 1 6 6 6 4 3 
0 2 1 2 6 6 4 3 
1 3 7 2 1 6...

result:

ok Accepted

Test #9:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

8
2
2
1
1
2
0
0
1
0
2
2
2
1
2
0
2
0

output:

0 1 3 2 6 4 7 5 8 
0 1 3 4 2 7 5 6 8 
0 3 5 6 7 2 8 1 4 
0 1 3 8 4 2 5 6 7 
0 8 2 7 6 3 5 4 1 
0 8 6 1 4 7 2 5 3 
0 4 4 4 4 3 3 3 3 
0 3 3 1 4 4 4 5 3 
0 8 6 3 3 4 4 5 3 
0 3 6 1 4 7 2 4 3 
0 8 2 2 2 6 6 5 6 
0 8 2 2 4 6 6 5 3 
0 8 2 1 4 6 2 5 3 
0 8 6 2 4 6 2 5 3 
0 8 5 1 5 7 7 5 7 
0 8 7 1 4 7 5 5...

result:

ok Accepted

Test #10:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

9
2
2
2
1
0
1
0
0
0
2
1
0
1
2
2
2
1
0
0
2

output:

0 3 5 7 1 6 2 9 4 8 
0 7 9 6 2 3 1 4 8 5 
0 5 7 3 8 2 6 4 1 9 
0 1 8 4 5 9 6 3 2 7 
0 9 5 3 2 1 4 6 7 8 
0 1 1 1 1 7 7 7 7 7 
0 9 5 3 2 7 7 7 7 7 
0 1 1 7 7 1 4 6 7 8 
0 7 5 1 2 1 4 6 7 8 
0 2 5 2 2 2 8 8 8 8 
0 2 5 2 2 1 8 8 7 8 
0 9 5 3 2 2 8 8 7 8 
0 2 5 3 2 1 4 6 8 8 
0 9 5 2 2 1 4 6 8 8 
0 3 5 ...

result:

ok Accepted

Test #11:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

10
1
2
4
2
0
2
1
0
1
2
1
0
2
1
0
1
0
1
1
0
0
0
0

output:

0 1 3 2 6 10 9 5 8 7 4 
0 1 9 5 3 10 7 4 8 2 6 
0 6 7 4 1 9 5 10 3 2 8 
0 7 9 8 1 2 3 5 4 6 10 
0 7 10 4 5 8 6 3 2 9 1 
0 10 10 10 10 10 6 6 6 6 6 
0 10 10 10 5 8 6 6 6 9 1 
0 7 10 4 10 10 6 6 6 9 1 
0 10 10 4 5 8 6 3 2 6 1 
0 7 10 10 5 8 6 3 2 6 1 
0 3 3 4 3 3 9 9 9 9 9 
0 7 10 4 5 8 9 9 9 9 9 
0 3...

result:

ok Accepted

Test #12:

score: 0
Accepted
time: 1ms
memory: 4024kb

input:

11
1
0
2
2
2
1
0
0
0
0
2
2
2
2
1
2
1
0
2
1
0

output:

0 11 5 7 1 6 2 10 4 8 9 3 
0 10 5 3 8 11 2 9 7 4 6 1 
0 3 3 3 3 3 4 4 4 4 4 4 
0 3 3 3 8 11 4 4 4 4 6 1 
0 3 3 3 8 11 4 4 7 4 6 1 
0 3 5 3 8 11 4 9 7 4 6 1 
0 10 3 3 8 11 4 9 7 4 6 1 
0 10 8 8 8 8 9 9 9 9 9 9 
0 10 9 9 8 11 8 9 8 8 6 1 
0 10 5 3 9 11 2 9 7 4 8 1 
0 10 7 7 7 11 5 9 5 5 5 1 
0 10 7 7 ...

result:

ok Accepted

Test #13:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

12
0
1
1
1
1
0
1
0
0
1
0
2
2
0
0
1
2
1
1
0
2
2
1
2
2

output:

0 1 3 2 6 10 12 5 8 7 11 4 9 
0 6 6 6 6 6 6 2 2 2 2 2 2 
0 1 3 2 6 10 12 2 2 2 2 2 2 
0 1 3 2 6 10 12 6 6 6 2 2 2 
0 1 3 2 6 10 12 5 8 7 2 2 2 
0 1 3 2 6 10 12 5 8 7 6 2 2 
0 1 3 2 6 10 12 5 8 7 2 6 9 
0 1 3 2 6 10 12 5 8 7 11 6 9 
0 12 12 12 12 12 3 3 3 3 11 3 9 
0 3 3 3 6 10 12 12 12 7 11 4 9 
0 1...

result:

ok Accepted

Test #14:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

13
0
0
0
0
0
1
0
1
0
1
2
1
1
0
1
2
2
1
0
0
2
2
1
2
2
2
1
0

output:

0 11 5 7 13 6 2 10 4 8 9 12 3 1 
0 3 3 3 3 3 3 5 5 5 5 5 5 5 
0 5 5 5 13 6 2 3 3 3 3 12 3 1 
0 11 5 7 5 5 2 10 4 8 9 3 3 1 
0 6 6 6 6 6 2 7 7 7 7 7 7 1 
0 7 7 7 13 6 2 6 6 6 9 12 3 1 
0 11 5 7 7 7 2 6 6 6 9 12 3 1 
0 7 7 7 13 6 2 10 4 8 6 6 3 1 
0 11 5 7 13 6 2 10 4 8 6 6 3 1 
0 7 5 7 13 6 2 10 4 8 ...

result:

ok Accepted

Test #15:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

14
0
0
0
1
2
2
0
2
1
0
2
0
2
1
2
2
0
1
0
2
1
1
0
1
0
2
1
0
0

output:

0 1 14 2 6 10 12 5 13 7 11 4 9 8 3 
0 6 6 6 6 6 6 6 4 4 4 4 4 4 4 
0 4 4 4 4 10 12 5 6 6 6 6 9 8 3 
0 1 14 2 6 4 4 5 13 7 11 4 6 6 3 
0 1 14 2 6 10 12 4 13 7 11 4 6 6 3 
0 1 14 2 6 10 12 4 13 7 11 4 6 8 3 
0 2 2 2 2 2 2 5 13 13 13 13 9 13 13 
0 13 13 13 6 10 12 5 2 2 2 4 9 8 3 
0 13 13 2 6 10 12 5 2...

result:

ok Accepted

Test #16:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

15
0
1
0
1
1
1
0
2
1
0
0
2
2
0
0
0
0
1
0
1
0
1
0
1
1
2
1
1
0
2
2
2

output:

0 11 5 7 13 6 2 10 14 8 15 12 3 1 4 9 
0 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 
0 11 5 7 13 6 2 10 9 9 9 9 9 9 9 9 
0 1 1 1 9 9 9 9 14 8 15 12 3 1 4 9 
0 11 5 7 9 9 9 9 14 8 15 12 3 1 4 9 
0 11 5 7 1 1 9 9 14 8 15 12 3 1 4 9 
0 11 5 7 13 6 9 9 14 8 15 12 3 1 4 9 
0 11 5 7 1 9 2 10 14 8 15 12 3 1 4 9 
0 15 1...

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 277ms
memory: 3964kb

input:

975
2
0
0
1
2
2
1
0
2
2
1
0
1
0
1
0
2
1
0
2
0
2
1
0
1
2
1
2
1
0
0
0
1
0
2
0
1
2
1
0
1
2
2
1
2
2
2
2
1
0
1
0
1
0
1
0
1
2
1
0
0
2
1
2
1
1
1
0
0
1
0
1
0
1
2
0
1
0
2
1
2
2
0
1
2
2
1
2
1
2
2
2
1
0
2
0
1
2
1
0
0
1
2
2
0
0
2
2
1
1
2
2
1
0
2
2
2
0
1
0
2
2
0
0
1
2
0
2
1
2
1
0
0
0
1
1
1
0
1
0
1
1
1
1
1
1
2
0
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 256ms
memory: 4036kb

input:

976
3
2
0
0
2
1
0
0
1
2
2
2
1
0
2
1
2
1
0
2
1
2
2
1
2
2
1
2
1
0
1
2
1
2
1
0
0
1
2
1
2
0
2
0
2
1
2
2
2
0
1
2
2
2
1
0
1
0
2
2
0
0
0
1
2
0
2
0
0
0
2
0
1
0
0
1
2
1
0
1
0
1
2
1
2
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
2
2
2
2
0
1
0
0
1
2
2
1
0
2
1
0
1
0
1
0
1
2
0
2
1
2
1
2
0
0
1
2
1
0
2
2
2
2
1
0
1
0
1
0
1
2
0
2
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #19:

score: 0
Accepted
time: 284ms
memory: 3980kb

input:

977
2
0
2
1
2
1
0
1
0
2
1
0
1
2
2
0
2
2
1
2
0
2
1
0
2
2
2
1
0
2
1
0
0
1
2
1
0
0
2
2
1
2
2
1
0
1
0
2
1
0
2
2
0
0
2
1
2
0
1
1
1
0
1
1
2
2
1
2
2
1
2
1
2
1
0
2
2
0
1
2
0
0
1
2
0
2
1
0
0
1
2
1
2
2
1
2
1
2
0
1
0
1
2
1
2
0
1
2
0
2
1
0
1
2
2
2
0
1
0
2
1
0
1
2
0
1
0
1
0
2
1
0
2
0
0
1
2
1
2
1
2
1
0
0
2
2
1
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #20:

score: 0
Accepted
time: 277ms
memory: 4044kb

input:

978
3
1
1
0
2
2
1
2
2
0
2
1
0
0
1
2
2
2
1
2
2
1
2
0
1
2
2
0
2
2
2
1
0
1
2
1
2
1
2
1
2
1
0
2
1
0
2
0
0
1
2
2
1
0
1
0
1
0
0
1
2
0
1
1
1
0
1
1
1
1
0
0
1
0
1
2
0
0
2
0
1
0
0
1
2
0
2
1
0
2
0
2
1
0
1
0
2
1
0
0
1
2
1
2
2
0
1
0
1
1
1
1
1
1
1
1
0
1
0
0
2
1
2
0
0
2
1
2
2
1
0
0
1
2
1
0
0
1
0
1
1
1
1
2
2
2
2
0
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 262ms
memory: 4004kb

input:

979
2
2
1
0
1
0
1
0
0
1
2
0
0
1
2
2
0
0
1
1
0
1
0
0
1
2
1
0
1
0
0
1
0
2
1
1
1
0
1
1
1
0
0
1
2
0
1
0
1
0
0
1
1
0
0
1
0
2
0
1
0
1
2
1
0
1
2
0
2
1
2
1
2
1
2
0
2
1
0
1
0
2
0
0
1
0
2
2
2
2
0
1
2
0
1
0
0
1
2
2
0
0
1
2
2
1
0
0
0
1
0
0
1
0
0
2
0
1
2
1
2
1
0
2
2
1
0
0
1
2
1
2
0
1
0
1
2
1
2
1
0
2
1
2
0
1
2
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 264ms
memory: 4068kb

input:

980
3
0
2
2
2
0
1
0
2
0
2
0
0
1
1
1
1
0
1
0
1
2
1
2
1
2
1
0
0
1
2
1
0
1
0
2
1
0
2
2
1
2
0
0
1
0
1
0
1
0
0
1
2
2
1
2
0
1
2
2
1
2
1
0
0
1
0
0
1
2
1
0
1
2
1
0
0
2
1
1
2
1
2
1
0
1
2
0
1
2
2
2
2
2
0
1
2
1
2
1
0
2
1
2
1
2
2
0
2
1
2
0
2
2
1
2
0
2
0
0
2
1
2
1
0
1
0
1
0
2
2
1
2
1
2
0
1
0
1
1
0
0
2
1
2
1
2
1
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 242ms
memory: 4092kb

input:

981
2
1
0
2
0
2
2
1
2
0
2
0
0
1
2
1
1
1
0
0
1
0
2
1
2
1
2
0
1
0
1
2
1
0
0
0
1
2
1
0
1
2
2
0
1
2
1
2
1
0
0
2
0
0
2
1
2
2
1
0
1
0
1
0
0
0
1
2
2
1
0
2
0
1
2
0
2
0
1
2
2
1
0
1
0
2
1
2
1
0
1
2
1
1
2
2
1
0
1
2
2
1
0
2
2
2
1
0
2
2
1
2
2
0
2
1
0
0
2
2
1
2
1
2
1
2
1
2
2
1
2
0
0
1
0
1
0
0
0
1
0
0
0
1
0
1
2
0
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 279ms
memory: 4104kb

input:

982
3
1
1
1
0
0
2
1
2
1
0
0
1
0
1
2
0
1
2
1
2
1
1
0
1
0
0
1
2
2
1
2
2
1
0
2
2
0
1
2
0
2
2
2
1
2
1
2
1
2
1
1
1
1
1
0
1
1
1
1
2
0
0
1
0
1
2
0
1
2
1
2
2
1
2
1
2
0
1
0
0
0
2
1
0
1
0
0
1
0
1
2
1
2
2
0
2
2
2
1
2
1
0
2
1
2
1
0
1
0
1
2
1
0
1
0
1
0
1
1
1
1
0
1
2
1
2
0
1
0
2
1
1
2
1
0
0
0
1
0
2
1
2
1
0
0
2
0
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #25:

score: 0
Accepted
time: 273ms
memory: 4052kb

input:

983
2
2
2
0
2
1
0
2
2
0
1
0
2
1
2
2
0
2
0
2
1
2
2
1
2
1
0
2
1
0
1
0
0
1
0
1
0
1
2
2
0
2
2
2
1
2
2
1
2
2
2
0
1
2
1
0
1
0
0
1
2
1
1
2
1
2
1
0
1
2
1
0
1
2
1
0
1
2
2
0
0
0
2
1
0
2
1
2
1
2
0
0
2
0
2
1
0
1
2
2
2
2
1
2
1
0
1
1
1
1
1
0
2
2
0
1
0
1
0
1
2
1
2
1
0
0
1
0
1
2
1
0
2
1
0
2
2
0
2
0
2
1
2
1
0
1
2
0
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 253ms
memory: 4336kb

input:

984
3
1
3
2
1
0
2
2
1
0
1
2
1
0
1
0
0
1
2
2
1
0
0
0
1
2
1
2
0
0
2
2
0
0
0
1
2
0
0
1
2
1
0
2
1
0
2
0
1
1
1
1
1
0
1
1
1
1
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
2
1
0
1
0
1
0
1
2
1
0
0
1
2
2
1
2
1
2
1
0
1
2
1
0
1
2
1
1
1
0
0
2
1
0
0
1
0
2
0
2
2
2
2
1
0
2
1
0
2
1
2
2
1
0
2
1
0
1
0
2
0
0
2
0
1
2
0
2
0
0
2
1
2
0
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 298ms
memory: 3992kb

input:

985
2
1
0
1
1
2
1
0
1
0
0
1
0
1
0
1
0
0
1
2
1
0
1
1
2
2
1
0
2
2
0
0
1
0
1
0
1
0
1
1
0
1
2
1
0
1
2
2
1
0
2
0
1
0
1
0
0
1
2
2
2
0
1
2
2
1
0
1
0
0
2
0
2
2
1
2
2
1
0
1
1
1
0
1
1
1
0
0
1
0
2
1
2
1
0
2
0
1
0
0
2
1
0
1
2
1
2
1
2
1
2
2
2
0
2
2
2
1
0
1
2
0
2
1
0
1
0
0
1
2
1
0
2
1
0
1
2
1
2
1
0
2
1
1
1
1
0
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #28:

score: 0
Accepted
time: 272ms
memory: 4036kb

input:

986
3
1
1
1
1
1
0
2
1
2
2
1
0
1
0
1
0
1
0
1
2
1
0
1
0
2
2
2
1
2
0
1
2
1
0
1
2
1
0
1
2
1
1
1
0
1
1
1
1
1
0
2
2
2
1
0
1
0
0
1
0
2
0
1
0
2
2
2
1
2
0
1
0
1
1
1
1
1
0
1
0
1
1
2
1
2
2
1
2
1
0
1
1
1
1
0
1
0
2
1
2
0
1
0
1
2
0
1
2
2
1
2
1
0
1
0
1
0
1
2
1
2
1
0
1
0
1
1
0
1
2
0
1
2
1
2
1
0
2
0
1
1
1
0
1
0
0
1
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 288ms
memory: 4052kb

input:

987
2
0
2
0
0
2
1
0
1
0
1
0
1
2
1
2
1
2
0
1
2
0
1
2
1
2
0
2
1
0
2
2
1
1
0
2
0
2
1
2
2
1
2
1
2
1
0
1
1
0
0
1
2
0
0
2
1
0
2
1
0
2
2
1
2
2
0
0
1
0
1
2
1
0
1
2
1
1
1
0
1
1
1
0
2
1
0
2
0
1
2
2
1
0
2
1
0
0
2
0
2
1
2
2
1
2
0
2
0
0
2
1
0
1
2
2
1
0
1
2
1
0
1
1
2
1
0
0
2
1
2
1
0
1
2
0
1
1
0
0
2
0
0
1
0
2
1
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 289ms
memory: 4036kb

input:

988
3
3
1
2
1
0
1
0
1
1
1
0
1
0
0
0
2
1
0
1
0
0
1
1
0
1
2
1
0
1
2
2
2
1
2
0
1
0
1
1
1
0
1
0
1
1
1
1
2
1
0
1
0
2
1
2
2
2
1
0
2
1
2
0
2
1
0
2
0
0
1
0
1
0
2
1
0
2
2
1
0
1
2
2
1
0
0
1
2
0
1
0
2
1
2
0
0
2
1
1
1
1
0
0
0
0
1
2
1
2
2
2
0
1
0
1
0
1
2
1
0
1
0
2
1
0
0
0
2
0
0
2
2
2
0
0
1
0
2
2
1
2
2
0
1
2
1
0
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 290ms
memory: 4132kb

input:

989
2
1
2
3
0
0
0
2
1
2
0
2
1
0
1
0
1
0
0
1
1
2
1
0
1
0
0
1
2
0
0
2
1
0
0
1
2
0
0
2
2
1
2
1
2
0
2
0
0
2
2
2
1
2
0
0
1
0
1
2
2
2
0
2
1
2
0
2
1
0
0
0
1
1
1
1
1
0
0
1
0
2
2
2
2
1
0
1
0
1
1
1
0
1
1
1
0
2
0
2
0
0
1
0
1
1
2
0
2
2
1
2
0
0
1
0
0
2
0
1
0
1
2
0
1
2
1
2
2
0
1
1
2
1
0
1
0
1
0
1
0
0
1
0
1
2
1
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 285ms
memory: 4332kb

input:

990
3
0
1
0
2
1
2
0
1
2
0
2
1
0
1
2
1
2
1
1
0
0
0
1
0
2
1
0
1
0
2
0
0
0
1
0
0
1
0
2
0
2
2
0
1
0
0
1
0
2
1
2
0
2
1
0
2
1
0
1
0
2
2
1
2
0
2
1
0
1
2
1
0
1
2
2
0
1
2
0
1
2
1
2
2
2
1
2
0
1
1
1
1
1
1
1
0
2
1
2
0
0
0
2
2
2
1
2
1
0
1
0
0
1
0
0
0
2
1
1
0
1
2
0
1
0
1
0
0
1
0
0
2
2
1
2
1
0
0
1
0
0
0
2
1
0
1
0
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 635 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 300ms
memory: 4020kb

input:

991
2
2
2
0
1
0
2
1
0
0
1
2
1
2
1
2
1
0
0
1
2
1
1
0
2
2
2
1
0
2
0
1
0
1
0
1
1
1
1
0
2
1
2
0
0
0
2
2
1
0
2
2
1
2
0
1
0
2
2
1
0
0
1
0
2
1
0
1
2
1
0
2
1
2
2
2
1
2
2
2
0
0
1
0
2
2
2
1
2
1
2
1
0
0
1
0
0
2
2
1
2
2
2
1
0
1
1
1
1
1
1
1
0
1
0
0
1
2
0
1
0
2
0
2
2
0
2
1
0
0
2
0
0
1
0
2
1
0
0
1
2
1
0
1
2
1
0
0
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #34:

score: 0
Accepted
time: 286ms
memory: 4412kb

input:

992
3
0
0
2
1
2
0
0
0
1
0
0
2
0
1
0
1
1
1
1
1
1
1
0
0
2
2
2
1
2
1
1
1
0
2
0
0
2
1
0
0
1
2
0
2
1
0
1
2
2
0
1
2
1
2
1
0
1
0
1
2
0
1
2
0
1
0
1
2
1
2
0
1
0
1
0
0
1
0
1
1
1
1
1
0
0
0
2
1
0
0
1
0
2
1
0
0
1
0
1
0
2
2
1
0
2
1
2
2
0
2
1
2
1
2
2
1
2
2
1
2
1
2
1
0
1
0
2
2
0
1
2
1
2
1
0
2
2
0
1
2
2
2
1
0
1
2
0
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 992 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #35:

score: 0
Accepted
time: 303ms
memory: 4040kb

input:

993
2
1
1
0
2
2
0
2
0
2
0
0
1
0
1
2
1
0
1
0
1
1
1
0
1
0
1
0
1
1
0
1
2
2
2
2
0
1
2
0
2
0
1
2
2
1
2
0
1
0
1
0
0
2
1
0
1
2
1
2
2
0
1
1
2
1
2
1
2
1
0
2
1
0
1
0
0
1
0
0
1
2
1
2
1
2
1
2
2
0
2
0
0
0
1
0
0
2
2
1
0
0
2
1
2
2
1
0
1
0
1
0
1
0
1
0
1
1
2
0
1
0
1
0
2
1
0
1
2
1
0
0
1
2
1
2
0
2
1
0
1
1
1
1
0
2
1
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #36:

score: 0
Accepted
time: 278ms
memory: 4160kb

input:

994
3
0
2
0
1
2
2
0
2
1
0
1
0
1
0
1
2
1
0
1
1
1
0
0
1
2
0
1
0
2
1
2
2
1
1
1
0
2
0
2
2
2
0
2
0
1
1
0
1
0
0
2
1
2
0
2
0
2
2
0
0
1
2
1
0
1
2
1
2
2
2
2
1
0
2
1
2
0
1
0
1
2
1
0
1
2
0
1
2
2
1
0
1
2
0
0
1
0
1
2
0
1
0
1
2
2
2
1
0
1
0
1
0
2
1
2
2
1
0
0
2
0
0
0
2
2
2
1
2
1
0
2
1
0
1
0
1
1
0
1
0
1
2
2
0
2
1
0
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 992 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #37:

score: 0
Accepted
time: 296ms
memory: 4056kb

input:

995
2
1
1
3
0
0
1
0
0
0
0
2
1
2
2
1
2
2
1
0
0
2
0
1
0
1
2
1
0
1
2
2
2
1
1
0
1
0
1
0
2
1
2
2
1
2
1
0
1
2
1
0
0
1
0
1
0
0
1
0
1
0
1
0
1
2
0
1
0
1
1
1
0
0
1
0
2
1
2
1
2
1
0
0
1
1
1
1
1
0
2
1
2
1
2
0
1
0
1
0
1
0
1
1
1
1
1
1
2
0
2
1
2
0
1
2
1
0
2
1
2
1
0
1
2
2
1
0
2
1
2
1
0
1
2
2
1
2
0
1
2
1
2
2
1
2
0
1
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 287ms
memory: 4408kb

input:

996
3
3
2
1
3
0
1
1
1
1
1
0
1
0
0
2
1
2
2
2
1
0
2
0
2
1
2
1
0
1
2
1
2
2
1
0
1
0
1
1
2
1
0
1
2
2
1
2
1
0
0
0
1
0
1
1
0
1
0
1
2
2
0
1
0
2
2
0
2
1
0
1
2
1
2
2
1
0
2
2
0
1
2
0
1
0
1
0
0
1
2
1
2
1
2
1
2
1
0
0
1
1
1
0
1
1
1
1
0
0
0
1
0
0
2
1
0
0
0
2
1
2
0
1
2
2
1
2
1
2
1
1
0
2
1
2
1
2
2
1
0
1
0
1
2
2
0
1
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 992 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 275ms
memory: 4100kb

input:

997
2
0
1
0
0
1
0
0
1
2
0
1
0
2
1
0
1
2
1
1
1
1
2
2
1
2
1
0
2
0
0
0
0
0
1
2
0
1
0
1
0
1
2
1
2
1
2
1
0
1
0
1
0
0
1
0
1
0
0
1
2
2
0
2
2
2
2
0
2
0
1
0
2
1
2
0
1
1
1
0
1
0
2
1
0
1
0
0
1
2
2
2
1
1
1
1
1
1
1
0
1
1
1
0
1
1
2
2
1
2
2
1
0
1
2
0
1
0
1
0
2
0
1
2
1
2
1
1
0
2
1
0
2
1
0
2
2
1
0
2
2
1
0
0
1
2
1
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 303ms
memory: 4336kb

input:

998
3
1
1
0
2
1
0
2
0
0
1
2
2
1
2
2
2
2
0
1
2
2
1
2
2
2
0
1
2
0
2
0
1
2
1
2
1
2
1
0
1
2
0
2
2
0
1
0
1
0
1
0
1
2
1
0
0
1
0
0
1
2
2
1
0
1
0
1
2
2
1
2
0
0
1
0
2
2
0
2
1
0
2
1
0
1
2
2
2
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
0
0
1
1
1
0
2
1
0
0
2
2
1
0
1
2
1
2
0
0
1
2
1
2
2
1
2
0
1
2
1
0
1
0
1
1
1
0
1
0
1
...

output:

0 883 397 137 546 570 299 710 665 520 505 659 948 693 794 814 105 644 857 547 692 817 992 717 933 189 84 277 296 474 732 14 183 651 642 746 762 727 782 538 83 378 764 11 884 795 217 793 96 369 535 257 368 451 108 531 821 119 237 587 103 193 636 292 18 956 51 187 791 892 486 276 529 174 192 25 288 61...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 300ms
memory: 4056kb

input:

999
2
2
0
0
0
1
0
0
1
0
2
1
0
0
2
0
1
1
1
1
2
2
2
0
1
2
1
2
0
2
1
1
1
0
1
0
0
2
0
2
0
1
2
1
0
0
2
0
0
1
0
2
2
0
1
0
1
2
2
0
2
2
1
2
0
1
0
1
0
0
1
2
0
1
0
0
1
2
0
0
1
0
2
1
0
2
2
1
0
2
1
2
1
0
1
0
2
0
0
0
0
2
1
2
2
0
1
0
1
2
1
2
2
1
0
1
1
1
0
1
1
2
1
0
1
2
0
1
0
0
2
1
1
1
0
1
0
2
0
1
0
1
2
0
1
0
1
2
...

output:

0 884 398 199 364 697 300 433 666 28 675 660 302 694 725 479 347 455 858 548 40 818 636 718 934 190 255 278 246 963 431 37 233 652 123 33 869 728 686 242 937 281 239 89 885 796 341 794 92 803 536 943 607 452 147 713 822 120 74 588 795 104 194 189 213 495 257 85 792 86 382 127 530 207 611 29 291 618 ...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed