QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744075#9432. Permutationktq_cppAC ✓289ms4132kbC++142.0kb2024-11-13 20:46:412024-11-13 20:46:45

Judging History

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

  • [2024-11-13 20:46:45]
  • 评测
  • 测评结果:AC
  • 用时:289ms
  • 内存:4132kb
  • [2024-11-13 20:46:41]
  • 提交

answer

/*
https://qoj.ac/problem/9432
*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mpr make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
#define repe(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define pii pair<int,int>
#define ALL(v) v.begin(),v.end()
using namespace std;
void chkmax(int& x,int y){x=x>y? x:y;}
void chkmin(int& x,int y){x=x>y? y:x;}
const int N=1e3+5;
int n;
int ans[N],q[N];
int query(){
	printf("0 ");
	for(int i=1;i<=n;i++)printf("%d ",q[i]);
	printf("\n");
	cout.flush();
	int x;
	scanf("%d",&x);
	return x;
}
int fa[N];
bool flag[N];
int getfa(int x){
	return fa[x]=(fa[x]==x? x:getfa(fa[x]));
}
void solve(int l,int r,vector<int> v){
	if(l==r){
		ans[l]=v[0];
		return;
	}
	int mid=l+r>>1;
	vector<int> L,R,del;
	for(auto x:v)fa[x]=x;
	while((int)v.size()>1){
		random_shuffle(v.begin(),v.end());
		int x=v.back();v.pop_back();
		int y=v.back();v.pop_back();
		for(int i=1;i<=n;i++){
			q[i]=(i<=mid? x:y);
		}
		int val=query();
		if(val==0)flag[x]=1,flag[y]=0,L.push_back(y),R.push_back(x);
		else if(val==2)flag[x]=0,flag[y]=1,L.push_back(x),R.push_back(y);
		else v.push_back(x),del.push_back(y),fa[y]=x;
	}
	if(!v.empty()){
		int x=v[0],val;
		if(!L.empty()){
			int y=L[0];
			for(int i=1;i<=n;i++){
				q[i]=(i<=mid? x:y);
			}
			val=query();
			if(val==0)R.push_back(x),flag[x]=1;
			else L.push_back(x),flag[x]=0;
		}
		else{
			int y=R[0];
			for(int i=1;i<=n;i++){
				q[i]=(i<=mid? x:y);
			}
			val=query();
			if(val==0)R.push_back(x),flag[x]=1;
			else L.push_back(x),flag[x]=0;
		}
	}
	for(auto y:del){
		int x=getfa(y);
		if(flag[x])R.push_back(y);
		else L.push_back(y);
	}
	if(!L.empty())solve(l,mid,L);
	if(!R.empty())solve(mid+1,r,R);
	return;
}
signed main(){
	scanf("%d",&n);
	if(n==1){
		puts("1 1");
		return 0;
	}
	vector<int> v;
	for(int i=1;i<=n;i++)v.push_back(i);
	solve(1,n,v);
	printf("1 ");
	for(int i=1;i<=n;i++)printf("%d ",ans[i]);cout.flush();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
0
1
0
1
2
0
0

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 951 95...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
0
1
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
2
0
0

output:

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

result:

ok Accepted

Test #7:

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

input:

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

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 494 49...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 754 75...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 82...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 592 59...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 976 97...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 29...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 908 90...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 97...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 239ms
memory: 4120kb

input:

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

output:

0 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 21...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 764 76...

result:

ok Accepted

Test #28:

score: 0
Accepted
time: 268ms
memory: 4112kb

input:

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

output:

0 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 841 84...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 327 32...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 788 78...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 775 77...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 5...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 268ms
memory: 3832kb

input:

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

output:

0 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 8...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 400 40...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 28...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 405 40...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 61...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 281ms
memory: 4120kb

input:

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

output:

0 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 14...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 612 61...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 801 80...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 628 62...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed