QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#606120#9432. PermutationyhdddAC ✓315ms4456kbC++204.6kb2024-10-02 22:15:342024-10-02 22:15:34

Judging History

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

  • [2024-10-02 22:15:34]
  • 评测
  • 测评结果:AC
  • 用时:315ms
  • 内存:4456kb
  • [2024-10-02 22:15:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
const int MAX = 3e3 + 10;

int b[MAX];
int n;

mt19937 Rnd(1),Rnd2(time(0));

int Tim;

int judge(vector <int> ans){
	for(int i:ans)printf("%lld ",i);printf("\n");fflush(stdout);
	// ++Tim;
	// if(ans[0] == 1){
		// for(int i = 1; i <= n; i++){
			// if(ans[i] != b[i])	return 0;
		// }
		// return 1;
	// }else{
		// int cnt = 0;
		// for(int i = 1; i <= n; i++){
			// if(ans[i] == b[i])	cnt++;	
		// }
		// return cnt;
	// }
	int x;cin>>x;
	return x;
}
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
const int maxn=1010;
int ans[maxn];
#define mid (l+r>>1)
#define ls nd<<1
#define rs nd<<1|1
vector<int> tree[maxn<<2];
vector<int> id[maxn];
int pl[maxn<<2],pr[maxn<<2];
void build(int nd,int l,int r,int dep){
	pl[nd]=l,pr[nd]=r;id[dep].pb(nd);
	if(l==r)return ;
	build(ls,l,mid,dep+1),build(rs,mid+1,r,dep+1);
}
bool vis[maxn];
void dfs(int dep){
	if(!id[dep].size())return ;
	for(int nd:id[dep]){
		int l=pl[nd],r=pr[nd];
		// cout<<dep<<" "<<l<<" "<<r<<" "<<nd<<endl;
		// for(int i:tree[nd])cout<<i<<" ";cout<<"\n";
		if(l==r){
			ans[l]=tree[nd].front();
		}
	}
	while(1){
		bool fl=0;
		for(int nd:id[dep]){
			int l=pl[nd],r=pr[nd];
			// cout<<l<<" "<<r<<" "<<tree[nd].size()<<" "<<tree[ls].size()<<" "<<tree[rs].size()<<" a\n";
			if(l==r)continue;
			if(tree[ls].size()==mid-l+1){
				while(tree[nd].size()){
					tree[rs].pb(tree[nd].back());
					tree[nd].pop_back();
				}
				continue;
			}
			if(tree[rs].size()==r-mid){
				while(tree[nd].size()){
					tree[ls].pb(tree[nd].back());
					tree[nd].pop_back();
				}
				continue;
			}
			fl=1;
		}
		if(!fl)break;
		vector<int> que(n+1);que[0]=0;
		fl=0;pii p={0,0};
		int pos=0;
		for(int nd:id[dep]){
			int l=pl[nd],r=pr[nd];
			if(l==r){
				int x=tree[nd].back()==1?2:1;
				que[l]=x;
				continue;
			}
			if(!tree[nd].size()){
				for(int i=l;i<=mid;i++)que[i]=tree[rs].back();
				for(int i=mid+1;i<=r;i++)que[i]=tree[ls].back();
				continue;
			}
			if(fl){
				for(int i=l;i<=mid;i++)que[i]=p.fi;
				for(int i=mid+1;i<=r;i++)que[i]=p.fi;
				continue;
			}
			shuffle(tree[nd].begin(),tree[nd].end(),Rnd);
			int u=tree[nd].back();tree[nd].pop_back();
			int v=tree[nd].back();tree[nd].pop_back();
			for(int i=l;i<=mid;i++)que[i]=u;
			for(int i=mid+1;i<=r;i++)que[i]=v;
			p={u,v};fl=1;pos=nd;
		}
		int val=judge(que);
		// cout<<p.fi<<" "<<p.se<<" "<<pos<<" "<<val<<"\n";
		// for(int i:tree[1])cout<<i<<" ";cout<<"\n";
		if(!val){
			int nd=pos;
			tree[ls].pb(p.se),tree[rs].pb(p.fi);
			continue;
		}
		if(val==2){
			int nd=pos;
			tree[ls].pb(p.fi),tree[rs].pb(p.se);
			continue;
		}
		if(dep==1&&tree[1].size()==n-2){
			tree[pos].pb(p.fi),tree[pos].pb(p.se);
			continue;
		}
		else{
			int nd=pos,x=1,l=pl[nd],r=pr[nd];
			if(tree[ls].size()){
				for(int i=mid+1;i<=r;i++)que[i]=tree[ls].back();
				int val=judge(que);
				if(val==1){
					tree[ls].pb(p.fi),tree[ls].pb(p.se);
				}
				else{
					tree[rs].pb(p.fi),tree[rs].pb(p.se);
				}
				continue;
			}
			if(tree[rs].size()){
				for(int i=l;i<=mid;i++)que[i]=tree[rs].back();
				int val=judge(que);
				if(val==1){
					tree[rs].pb(p.fi),tree[rs].pb(p.se);
				}
				else{
					tree[ls].pb(p.fi),tree[ls].pb(p.se);
				}
				continue;
			}
			for(int i:tree[nd])vis[i]=1;
			for(int i:tree[ls])vis[i]=1;
			for(int i:tree[rs])vis[i]=1;
			vis[p.fi]=vis[p.se]=1;
			while(vis[x])x++;
			for(int i:tree[nd])vis[i]=0;
			for(int i:tree[ls])vis[i]=0;
			for(int i:tree[rs])vis[i]=0;
			vis[p.fi]=vis[p.se]=0;
			for(int i=mid+1;i<=r;i++)que[i]=x;
			int val=judge(que);
			if(val==1){
				tree[ls].pb(p.fi),tree[ls].pb(p.se);
			}
			else{
				tree[rs].pb(p.fi),tree[rs].pb(p.se);
			}
		}
	}
	// cout<<dep<<"\n";
	dfs(dep+1);
}

void solve(){
	cin >> n;
	if(n == 1){
		cout << "1 1";
		return ;
	}
	for(int i = 1; i <= n; i++){
		b[i] = i;
	}
	
	shuffle(b + 1, b + n + 1, Rnd2);
	// for(int i = 1; i <= n; i++){
		// cin >> b[i];
	// }
	// for(int i = 1; i <= n; i++)	cout << b[i] << ' ';cout << '\n';fflush(stdout);
	for(int i=1;i<=n;i++)tree[1].pb(i);
	build(1,1,n,1);
	dfs(1);
	vector<int> a(n+1);
	a[0]=1;for(int i=1;i<=n;i++)a[i]=ans[i];
	printf("1 ");for(int i=1;i<=n;i++)printf("%lld ",ans[i]);fflush(stdout);
	// if(judge(a))cout<<"ac\n";
	// else cout<<"wa\n";
	// cout<<Tim<<"\n";
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}

詳細信息

Test #1:

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

input:

5
0
0
0
0
2

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 37...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
0

output:

0 1 2 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
1
1
1
1
2
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
1
1
1
1
2
0
2
2

output:

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

result:

ok Accepted

Test #7:

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

input:

6
0
1
1
1
1
0
0
0

output:

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

result:

ok Accepted

Test #8:

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

input:

7
2
0
2
2
0
1
1
0
0
0

output:

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

result:

ok Accepted

Test #9:

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

input:

8
0
2
0
2
0
0
2
0
0
0
0
0

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

0 14 14 14 14 14 14 14 6 6 6 6 6 6 6 
0 7 7 7 7 7 7 7 10 10 10 10 10 10 10 
0 7 7 7 7 7 7 7 14 14 14 14 14 14 14 
0 5 5 5 5 5 5 5 11 11 11 11 11 11 11 
0 5 5 5 5 5 5 5 10 10 10 10 10 10 10 
0 1 1 1 1 1 1 1 4 4 4 4 4 4 4 
0 1 1 1 1 1 1 1 10 10 10 10 10 10 10 
0 8 8 8 8 8 8 8 12 12 12 12 12 12 12 
0 8...

result:

ok Accepted

Test #16:

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

input:

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

output:

0 4 4 4 4 4 4 4 4 9 9 9 9 9 9 9 
0 6 6 6 6 6 6 6 6 12 12 12 12 12 12 12 
0 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 
0 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 
0 2 2 2 2 2 2 2 2 11 11 11 11 11 11 11 
0 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 
0 6 6 6 6 6 6 6 6 4 4 4 4 4 4 4 
0 13 13 13 13 13 13 13 13 14 14 14 14 14...

result:

ok Accepted

Test #17:

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

input:

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

output:

0 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 912 91...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 877 87...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 891 89...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 497 49...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 10...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 446 44...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 753 75...

result:

ok Accepted

Test #25:

score: 0
Accepted
time: 302ms
memory: 4188kb

input:

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

output:

0 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 94...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 948 94...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 291ms
memory: 4452kb

input:

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

output:

0 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 553 55...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 268 26...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 291ms
memory: 4352kb

input:

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

output:

0 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 726 72...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 952 95...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 419 41...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 769 76...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 297ms
memory: 3984kb

input:

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

output:

0 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 946 94...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 474 47...

result:

ok Accepted

Test #35:

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

input:

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

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

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

input:

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

output:

0 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 984 98...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 880 88...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 308ms
memory: 4456kb

input:

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

output:

0 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 557 55...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 302ms
memory: 4452kb

input:

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

output:

0 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 455 45...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 25...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 33...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed