QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#615713#9432. PermutationyyyyxhAC ✓282ms4164kbC++142.7kb2024-10-05 19:51:382024-10-05 19:51:39

Judging History

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

  • [2024-10-05 19:51:39]
  • 评测
  • 测评结果:AC
  • 用时:282ms
  • 内存:4164kb
  • [2024-10-05 19:51:38]
  • 提交

answer

#include <cstdio>
#include <bitset>
#include <random>
#include <cassert>
#include <algorithm>
using namespace std;
mt19937 rng(random_device{}());
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=1003;
bitset<N> a[N];int c[N];
int n,cnt;
int p[N];
int w[N],s[N];
int ask(){
	int res=0;
	++cnt;
#ifdef LOCAL
	for(int i=1;i<=n;++i) res+=(p[i]==w[i]);
#else
	putchar('0');
	for(int i=1;i<=n;++i) printf(" %d",w[i]);
	putchar('\n');fflush(stdout);
	res=read();
#endif
	return res;
}
int stk[N],tp;
void proc(){
	for(int i=1;i<=n;++i) w[i]=rng()%n+1;
	while(ask()) for(int i=1;i<=n;++i) w[i]=rng()%n+1;
}
int res[N];
vector<int> lis[N];
void solve(int l,int r,vector<int> vc){
	if(l==r){res[l]=vc.back();return;}
	shuffle(vc.begin(),vc.end(),rng);
	vector<int> lef,rig;
	int mid=(l+r)>>1;
	for(int x:vc) lis[x].emplace_back(x);
	while(vc.size()>1){
		int x=vc.back();vc.pop_back();
		int y=vc.back();vc.pop_back();
		for(int i=1;i<=n;++i) w[i]=s[i];
		for(int i=l;i<=mid;++i) w[i]=x;
		for(int i=mid+1;i<=r;++i) w[i]=y;
		int v=ask();
		if(v==0){
			for(int t:lis[x]) rig.emplace_back(t);
			for(int t:lis[y]) lef.emplace_back(t);
			lis[x].clear();lis[y].clear();
			continue;
		}
		if(v==2){
			for(int t:lis[x]) lef.emplace_back(t);
			for(int t:lis[y]) rig.emplace_back(t);
			lis[x].clear();lis[y].clear();
			continue;
		}
		if(lis[x].size()<lis[y].size()) swap(x,y);
		for(int t:lis[y]) lis[x].emplace_back(t);
		lis[y].clear();
		vc.emplace_back(x);
		if((int)lef.size()==mid-l+1){
			while(!vc.empty()){
				for(int t:lis[vc.back()]) rig.emplace_back(t);
				lis[vc.back()].clear();
				vc.pop_back();
			}
			break;
		}
		if((int)rig.size()==r-mid){
			while(!vc.empty()){
				for(int t:lis[vc.back()]) lef.emplace_back(t);
				lis[vc.back()].clear();
				vc.pop_back();
			}
			break;
		}
	}
	while(!vc.empty()){
		int x=vc.back();vc.pop_back();
		for(int i=1;i<=n;++i) w[i]=s[i];
		for(int i=l;i<=mid;++i) w[i]=x;
		if(ask()) for(int t:lis[x]) lef.emplace_back(t);
		else for(int t:lis[x]) rig.emplace_back(t);
		lis[x].clear();
	}
	solve(l,mid,lef);
	solve(mid+1,r,rig);
}
int main(){
	n=read();
#ifdef LOCAL
	for(int i=1;i<=n;++i) p[i]=i;
	shuffle(p+1,p+n+1,rng);
#endif
	if(n==1){
		puts("1 1");
		return 0;
	}
	proc();
	vector<int> init;
	for(int i=1;i<=n;++i) s[i]=w[i],init.emplace_back(i);
	solve(1,n,init);
	putchar('1');
	for(int i=1;i<=n;++i) printf(" %d",res[i]);
	putchar('\n');
	fflush(stdout);
	fprintf(stderr,"%d\n",cnt);
#ifdef LOCAL
	for(int i=1;i<=n;++i) assert(res[i]==p[i]);
#endif
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4020kb

input:

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

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 190 161 957 256 415 233 100 915 834 134 302 893 404 413 364 847 718 126 411 434 787 411 882 207 748 635 661 132 249 16 314 682 573 195 230 667 363 162 2 942 59 910 718 421 741 41 725 319 376 532 403 200 546 965 795 610 111 218 490 200 765 352 837 239 928 797 224 919 774 401 806 156 49 939 365 957 ...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

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: 3636kb

input:

3
2
1
0
2
1
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
0
1
0
1
2
2

output:

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

result:

ok Accepted

Test #7:

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

input:

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

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 258ms
memory: 3868kb

input:

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

output:

0 63 848 416 777 813 841 75 4 288 378 19 826 32 319 849 711 615 306 21 617 286 133 790 553 731 338 292 231 272 557 405 767 774 267 715 514 827 496 234 314 632 349 102 834 902 931 6 355 338 170 64 402 800 686 848 163 244 260 774 805 522 461 49 371 695 79 503 71 774 288 50 565 30 954 904 34 511 152 66...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 246ms
memory: 3840kb

input:

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

output:

0 739 59 717 218 453 755 449 534 369 854 309 871 252 908 634 676 587 434 749 42 551 26 640 498 969 461 714 134 574 826 135 286 817 250 947 30 299 449 61 750 235 421 291 276 71 87 241 315 406 884 692 389 381 716 860 671 582 303 343 664 154 941 633 643 370 278 281 58 287 246 766 730 965 377 115 101 13...

result:

ok Accepted

Test #19:

score: 0
Accepted
time: 233ms
memory: 3868kb

input:

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

output:

0 702 550 382 65 866 50 156 475 484 528 711 641 208 359 413 262 650 637 714 69 957 500 652 869 98 659 547 944 670 618 630 780 208 263 596 724 322 867 300 209 853 441 896 84 562 742 132 349 90 199 90 431 903 749 289 234 258 538 680 493 2 360 897 644 819 355 656 837 53 357 709 848 895 593 579 584 187 ...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 36 425 31 435 354 272 494 758 416 961 775 256 421 970 324 788 317 615 333 211 978 255 850 505 33 661 184 350 212 532 355 882 491 365 427 172 27 28 57 71 143 195 251 146 512 584 544 693 48 769 336 346 498 352 293 622 263 404 363 412 711 401 254 298 910 479 796 442 444 936 697 859 330 916 27 626 702...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 282ms
memory: 3872kb

input:

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

output:

0 347 652 609 341 202 715 163 473 567 301 827 520 931 185 195 611 523 424 394 936 877 966 668 591 362 963 225 902 783 495 629 836 346 870 606 943 683 148 364 375 53 78 534 422 824 309 163 944 562 83 362 472 113 866 434 78 209 157 904 563 234 461 623 765 275 508 853 767 529 848 621 67 356 87 371 880 ...

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 250ms
memory: 3796kb

input:

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

output:

0 538 59 900 314 190 126 681 604 938 429 852 194 448 681 777 492 946 368 802 54 226 858 351 269 144 553 872 645 67 271 940 338 377 323 291 323 832 677 834 208 89 141 831 424 523 849 726 491 723 585 143 134 656 162 229 60 467 739 953 81 644 445 647 894 891 936 620 774 851 210 426 79 465 559 895 959 6...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 271ms
memory: 3828kb

input:

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

output:

0 176 467 231 287 806 23 619 412 871 544 350 975 834 536 938 816 444 91 231 838 452 968 821 465 931 628 932 421 468 349 170 927 697 857 644 198 937 30 874 408 801 155 421 784 764 197 687 649 670 93 967 915 423 251 573 68 98 118 254 428 951 5 280 573 41 488 499 919 621 935 54 551 301 411 914 764 59 3...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 250ms
memory: 3872kb

input:

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

output:

0 588 759 94 967 904 904 907 295 215 294 658 590 588 147 800 721 26 410 325 334 113 390 690 275 675 160 637 398 614 679 896 196 94 402 120 831 618 788 764 976 249 483 366 444 375 127 477 728 201 931 570 152 266 234 864 358 447 871 583 710 491 626 511 766 851 412 285 650 80 745 523 809 905 547 939 83...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 781 916 120 508 399 486 15 674 389 52 405 667 410 65 470 94 722 635 498 400 261 560 107 963 310 622 115 510 862 135 416 194 459 64 233 586 401 511 553 133 573 268 752 148 5 754 589 500 721 681 657 690 242 818 892 65 734 982 760 233 702 772 58 776 562 953 733 922 774 15 535 731 114 93 921 738 785 6...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 276ms
memory: 4164kb

input:

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

output:

0 614 946 895 682 932 936 855 758 243 327 810 737 251 398 15 664 404 692 957 290 273 147 724 473 521 544 326 844 872 908 842 190 779 306 747 879 672 921 419 870 665 305 258 838 366 131 55 3 540 270 70 153 164 456 637 309 47 559 714 295 450 309 600 941 845 345 507 536 244 790 456 517 440 225 975 121 ...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 185 160 747 823 796 151 42 292 62 519 641 363 735 549 849 74 103 170 594 140 1 209 467 648 42 651 193 958 212 966 977 43 438 935 305 97 805 380 245 378 188 653 661 512 860 76 81 480 398 66 671 525 701 752 764 943 443 463 308 436 845 749 107 287 297 194 978 707 654 577 230 461 461 247 146 409 695 5...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 586 74 92 87 395 340 467 937 418 890 537 738 960 790 168 501 115 393 473 51 881 958 187 727 728 943 324 670 635 85 483 638 577 281 419 673 499 840 60 560 335 617 709 31 685 13 392 545 427 771 45 870 597 978 910 668 315 610 774 977 80 292 531 578 945 257 189 75 533 544 266 767 330 37 328 176 805 79...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 226ms
memory: 3996kb

input:

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

output:

0 775 370 691 322 82 791 697 482 891 242 738 580 368 702 155 887 487 686 291 624 717 834 271 547 853 946 633 273 834 189 724 598 874 593 638 474 388 703 517 907 108 291 70 876 19 754 543 859 432 896 257 486 612 271 373 900 360 181 169 822 100 90 709 393 16 532 224 402 625 548 814 880 327 415 946 213...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 232ms
memory: 3864kb

input:

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

output:

0 668 355 567 287 689 143 741 476 870 864 977 166 821 585 303 880 773 200 735 397 440 977 93 229 874 386 122 267 387 538 46 546 279 153 594 109 394 554 386 611 124 129 783 719 212 633 777 195 141 686 28 897 203 624 304 278 404 913 38 91 116 185 344 123 467 513 732 808 181 754 25 512 485 352 386 685 ...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 269ms
memory: 3780kb

input:

989
4
0
1
0
1
0
0
1
1
0
2
1
1
2
1
1
1
0
2
0
0
2
2
1
1
2
2
1
1
0
0
1
1
2
1
1
1
2
2
2
1
0
0
0
0
1
1
1
0
1
0
1
1
2
1
1
2
1
1
1
1
2
2
1
0
1
2
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
1
2
0
2
1
0
1
1
1
1
0
0
1
0
1
1
0
1
1
2
1
0
1
0
1
1
1
2
2
0
2
2
2
0
1
1
1
1
2
0
1
1
0
0
1
1
1
0
0
2
2
0
0
1
2
0
1
0
1
0
0
0
1
2
0
1
...

output:

0 723 142 554 153 478 704 498 744 880 688 941 167 658 52 936 470 711 398 583 985 451 513 823 229 941 59 983 321 839 582 282 853 306 363 589 214 46 697 746 447 728 840 403 712 267 567 847 577 88 227 231 845 600 743 742 565 960 633 225 605 321 530 485 916 558 174 568 850 598 474 440 557 979 93 39 682 ...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 265ms
memory: 3864kb

input:

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

output:

0 453 669 739 937 940 776 817 990 311 414 917 741 939 611 247 935 303 805 279 599 804 762 251 344 107 435 970 148 752 446 884 643 128 837 701 226 410 281 460 786 860 576 753 280 149 594 585 491 777 87 96 358 533 550 568 152 509 285 436 900 873 457 122 23 585 607 837 185 678 470 393 934 865 279 124 4...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 521 534 950 371 799 365 761 599 831 106 736 663 816 467 128 473 503 772 704 80 10 63 879 34 621 92 748 475 779 795 59 12 391 871 89 30 176 455 595 788 788 129 799 506 511 780 300 432 332 118 43 243 758 66 667 908 174 651 849 406 315 331 60 613 660 132 634 491 29 730 16 736 659 885 557 783 11 954 8...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 580 858 427 35 538 562 360 165 439 293 521 124 702 641 339 240 756 372 92 330 763 633 245 921 758 51 867 239 197 827 137 481 336 565 947 755 82 560 915 341 931 340 632 565 145 655 331 581 13 255 465 659 809 382 728 308 189 844 192 587 344 578 890 442 860 427 217 545 470 622 393 218 414 662 401 646...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 854 606 873 744 879 762 992 312 102 419 782 50 19 593 745 730 515 232 187 329 183 862 966 832 688 754 102 982 75 515 427 420 989 566 809 988 553 140 30 95 481 322 982 72 29 897 154 983 27 347 927 204 19 552 954 162 31 246 138 665 492 872 584 241 250 70 554 488 490 507 185 745 401 330 79 333 140 59...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 769 733 549 54 839 902 208 586 866 849 510 325 195 795 19 954 377 50 886 16 970 67 500 508 889 320 105 211 101 289 978 235 707 604 401 987 412 664 386 811 239 677 663 374 636 252 360 418 960 773 537 571 141 335 951 968 65 899 764 750 771 72 99 861 734 489 391 795 578 642 10 593 97 626 721 186 553 ...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 445 785 921 23 321 390 451 315 804 190 74 841 516 655 144 436 661 929 750 441 684 119 984 152 729 568 57 179 816 954 856 306 596 50 852 891 894 7 693 419 848 216 634 11 176 657 902 396 815 125 118 364 631 864 870 189 526 150 789 662 323 952 636 900 799 901 907 278 886 778 294 806 15 416 707 926 49...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 877 810 202 418 229 937 199 840 834 434 435 883 282 445 723 745 225 900 37 531 908 638 265 245 302 800 754 570 598 906 610 962 692 564 732 277 963 109 826 342 540 537 461 498 677 928 506 649 737 876 866 898 77 857 71 487 446 546 492 625 982 568 139 266 744 299 121 543 621 418 555 178 405 587 147 1...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 266ms
memory: 3840kb

input:

997
1
4
2
3
1
2
2
1
0
0
0
1
0
0
1
0
1
1
1
1
1
1
1
2
1
1
1
1
2
1
0
1
0
1
1
2
1
1
2
1
1
2
0
0
0
1
0
2
1
0
0
1
0
1
1
1
1
1
1
0
1
2
0
0
2
1
0
1
1
1
1
2
1
1
0
1
2
1
2
1
0
1
1
1
1
0
0
1
0
1
1
2
1
0
1
0
1
1
0
1
2
0
1
0
1
2
0
1
1
1
0
2
1
1
0
0
2
2
0
2
1
2
1
1
1
0
1
1
1
1
0
1
1
0
0
0
2
1
1
2
2
1
2
1
1
2
2
1
...

output:

0 115 40 793 790 410 685 395 234 146 265 270 823 357 722 268 883 519 804 316 70 397 245 273 514 177 586 779 457 521 236 745 56 312 617 271 440 289 451 640 755 109 880 916 99 64 182 208 252 37 84 310 742 695 198 745 926 947 85 840 628 90 336 740 875 968 186 150 520 60 25 491 579 533 101 519 605 86 71...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 438 882 517 987 987 11 692 265 864 319 931 437 100 410 845 559 799 204 88 261 843 809 890 59 944 954 613 668 795 941 127 334 796 636 478 972 894 913 189 99 127 9 526 134 27 320 901 581 496 662 584 685 328 768 943 666 393 157 106 7 562 227 826 887 442 573 475 824 70 456 418 334 562 193 730 191 714 ...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 270ms
memory: 3736kb

input:

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

output:

0 967 808 319 232 683 881 825 423 404 701 184 291 802 18 712 494 809 793 617 821 922 765 470 769 298 672 894 360 863 591 659 806 492 565 39 807 395 657 652 358 962 36 124 240 495 502 203 320 587 140 177 906 708 309 640 374 777 745 240 411 126 154 402 366 153 519 229 850 7 937 350 341 550 501 353 894...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed