QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#740388#9432. PermutationlichenghanAC ✓296ms4180kbC++143.0kb2024-11-13 09:36:342024-11-13 09:36:34

Judging History

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

  • [2024-11-13 09:36:34]
  • 评测
  • 测评结果:AC
  • 用时:296ms
  • 内存:4180kb
  • [2024-11-13 09:36:34]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
// #define SELF_TEST
using namespace std;
const int N=1e3+10;
mt19937 e(time(0));
// mt19937 e(0);
int n;
int hid[N];
void init_shuffle(){
	#ifdef SELF_TEST
		iota(hid+1,hid+n+1,1);
		shuffle(hid+1,hid+n+1,e);
		// printf("# ");
		// for(int i=1;i<=n;i++){
		// 	printf("%d ",hid[i]);
		// }
		// puts("");
	#endif
}
struct DSU{
	int fa[N];
	void init(const vector<int>& V){ for(int i:V) fa[i]=i; }
	int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
	void link(int u,int v){ fa[find(u)]=find(v); }
	bool same(int u,int v){ return find(u)==find(v); }
}T;
int zero[N];
int c_ask=0;
int ask(int l,int mid,int r,int ql,int qr){
	++c_ask;
	// [l==ql] + [r==qr]
	static int tmp[N];
	for(int i=1;i<l;i++) tmp[i]=zero[i];
	for(int i=n;i>r;i--) tmp[i]=zero[i];
	for(int i=l;i<=mid;i++) tmp[i]=ql;
	for(int i=mid+1;i<=r;i++) tmp[i]=qr;
	#ifdef SELF_TEST
		int ans=0;
		for(int i=1;i<=n;i++){
			ans+=(hid[i]==tmp[i]);
		}
		return ans;
	#else
		printf("0 ");
		for(int i=1;i<=n;i++){
			printf("%d ",tmp[i]);
		}
		puts(""); fflush(stdout);
		int ans=0;
		scanf("%d",&ans);
		return ans;
	#endif
}
int fin[N];
void answer(int x,int d){ fin[x]=d; }
void answer(){
	#ifdef SELF_TEST
		for(int i=1;i<=n;i++){
			if(fin[i]!=hid[i]){
				puts("Wrong answer!");
				printf("Hidden: ");
				for(int j=1;j<=n;j++) printf("%d ",hid[j]);
				puts("");
				printf("%d differs!\n",i);
			}
		}
		printf("Correct! count = %d\n",c_ask);
	#else
		printf("1 ");
		for(int i=1;i<=n;i++){
			printf("%d ",fin[i]);
		}
		puts(""); fflush(stdout);
	#endif
	exit(0);
}
void solve(int l,int r,const vector<int>& V){
	// printf("\nsolve %d %d [",l,r);
	// for(int i:V) printf("%d ",i);
	// puts("]");
	assert((int)V.size()==r-l+1);
	if(l==r){
		answer(l,V[0]);
		return;
	}
	T.init(V);
	int lef=0,rit=0;
	int mid=(l+r)>>1;
	auto sep=[&](int x,int y){
		if(!lef) lef=x,rit=y;
		else T.link(lef,x),T.link(rit,y);
	};
	auto sam=[&](int x,int y){
		T.link(x,y);
	};
	vector<int> cur=V;
	while(!cur.empty()){
		shuffle(cur.begin(),cur.end(),e);
		if(cur.size()==1){
			assert(lef);
			int ret=ask(l,mid,r,cur[0],lef);
			if(ret) sep(cur[0],rit);
			else sep(lef,cur[0]);
			break;
		}
		vector<int> nxt;
		for(int i=0;i+1<(int)cur.size();i+=2){
			int ret=ask(l,mid,r,cur[i],cur[i+1]);
			if(ret==0){
				sep(cur[i+1],cur[i]);
			}else if(ret==1){
				sam(cur[i],cur[i+1]);
				nxt.push_back(cur[i]);
			}else{
				sep(cur[i],cur[i+1]);
			}
		}
		if(cur.size()&1) nxt.push_back(cur.back());
		cur.swap(nxt);
	}
	vector<int> vl,vr;
	for(int i:V) {
		if(T.same(i,lef)){
			vl.push_back(i);
		}else{
			vr.push_back(i);
		}
	}
	for(int i=l;i<=mid;i++) zero[i]=rit;
	for(int i=mid+1;i<=r;i++) zero[i]=lef;
	solve(l,mid,vl);
	solve(mid+1,r,vr);
}
int main(){
	scanf("%d",&n);
	init_shuffle();
	vector<int> ful(n);
	iota(ful.begin(),ful.end(),1);
	solve(1,n,ful);
	answer();
}

详细

Test #1:

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

input:

5
2
0
1
0
1
0
0

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 394 39...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
0

output:

0 1 2 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
2
1
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
0
2
0
0

output:

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

result:

ok Accepted

Test #7:

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

input:

6
0
1
1
2
0
1
2
2
1
0

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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 1 1 1 1 1 1 1 
0 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 
0 12 12 12 12 12 12 12 12 14 14 14 14 14 14 14 
0 15 15 15 15 15 15 15 15 11 11 11 11 11 11 11 
0 10 10 10 10 10 10 10 10 8 8 8 8 8 8 8 
0 6 6 6 6 6 6 6 6 3 3 3 3 3 3 3 
0 2 2 2 2 2 2 2 2 7 7 7 7 7 7 7...

result:

ok Accepted

Test #17:

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

input:

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

output:

0 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 302 30...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 254ms
memory: 3900kb

input:

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

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 #19:

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

input:

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

output:

0 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 607 60...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 442 44...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 428 42...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 11...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 244ms
memory: 3904kb

input:

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

output:

0 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 567 56...

result:

ok Accepted

Test #24:

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

input:

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

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 #25:

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

input:

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

output:

0 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 257ms
memory: 3900kb

input:

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

output:

0 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 11...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 906 90...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 622 62...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 584 58...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 705 70...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 294ms
memory: 4176kb

input:

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

output:

0 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 903 90...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 269 26...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 143 14...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 960 96...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 744 74...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 781 78...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 620 62...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 469 46...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 735 73...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 13...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed