QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745282#9432. Permutationpiggy123AC ✓315ms4088kbC++174.5kb2024-11-14 08:56:372024-11-14 08:56:37

Judging History

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

  • [2024-11-14 08:56:37]
  • 评测
  • 测评结果:AC
  • 用时:315ms
  • 内存:4088kb
  • [2024-11-14 08:56:37]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll to[1005],ans[1005],f[1005],id[1005],vis[1005],n;
vector<ll> pp[1005]; 
mt19937 mt(time(0));

ll find(ll a){
	if(f[a]!=a)f[a]=find(f[a]);
	return f[a];
}

void merge(ll a,ll b){
	ll x=find(a),y=find(b);
	if (x==y)return;
	if (pp[x].size()>pp[y].size())swap(x,y);
	f[x]=y;
	for (ll i:pp[x])pp[y].push_back(i);
}

void solve(ll l,ll r,vector<ll>&all){
//	cout<<l<<","<<r<<":";
//	for (ll i:all)cout<<i<< ",";
//	cout<< endl;
	if (l==r){
		ans[l]=all[0];
		return;
	}
	vector<ll> cs;
	vector<ll> pl,pr;
	for (ll i=0;i<all.size();i++)pp[i+1].clear(),pp[i+1].push_back(i+1),cs.push_back(i+1),id[all[i]]=i+1,to[i+1]=all[i],f[i+1]=i+1,vis[all[i]]=1;
	ll non=0;
	for (ll i=1;i<=n;i++)if (vis[i])non=i;
	for (ll i=0;i<all.size();i++)vis[all[i]]=0;
	ll mid=(l+r)>>1; 
	while (cs.size()>1){
//		cout<<"? ";
//		for (ll i:cs)cout<<i<<" ";
//		cout<< endl;
		ll p1=cs[mt()%cs.size()],p2=cs[mt()%cs.size()];
		while (p1==p2)p2=cs[mt()%cs.size()];
		cout<<"0 ";
		for (ll i=1;i<l;i++)cout<<non<<" ";
		for (ll i=l;i<=mid;i++)cout<<to[find(p1)]<<" ";
		for (ll i=mid+1;i<=r;i++)cout<<to[find(p2)]<<" ";
		for (ll i=r+1;i<=n;i++)cout<<non<<" ";
		cout<< endl;
		ll x;
		cin >> x;
		if (x==0){
			cs.erase(find(cs.begin(),cs.end(),p1));cs.erase(find(cs.begin(),cs.end(),p2));
			for (ll i:pp[find(p2)])pl.push_back(to[i]);
			for (ll i:pp[find(p1)])pr.push_back(to[i]);
		}else if (x==2){
			cs.erase(find(cs.begin(),cs.end(),p1));cs.erase(find(cs.begin(),cs.end(),p2));
			for (ll i:pp[find(p1)])pl.push_back(to[i]);
			for (ll i:pp[find(p2)])pr.push_back(to[i]);
		}else{
			merge(p1,p2);
			cs.erase(find(cs.begin(),cs.end(),p1));cs.erase(find(cs.begin(),cs.end(),p2));
			cs.push_back(find(p1));
		}
	}
	if (cs.size()==1){
		if (pl.size()!=mid-l+1){
			for (ll i:pp[find(cs[0])])
			pl.push_back(to[i]);
		}
		if (pr.size()!=r-mid){
			for (ll i:pp[find(cs[0])])
			pr.push_back(to[i]);
		}
	}
	solve(l,mid,pl);
	solve(mid+1,r,pr);
}

int main(){
	cin >> n;
	vector<ll> all;
	for (ll i=1;i<=n;i++)all.push_back(i);
	solve(1,n,all);
	cout<< "1 ";
	for (ll i=1;i<=n;i++){
		cout<< ans[i]<<" ";
	}
	return 0;
}

/*
                                                                
 ■■■■■     ■■      ■■■     ■■■   ■    ■     ■     ■■■■    ■■■■  
 ■   ■■    ■■     ■  ■■   ■  ■■  ■    ■    ■■     ■  ■■  ■■  ■  
 ■    ■    ■■    ■    ■  ■    ■   ■  ■    ■■■    ■■  ■■  ■   ■■ 
 ■    ■    ■■    ■    ■  ■    ■   ■  ■     ■■    ■   ■■      ■■ 
 ■    ■    ■■    ■       ■         ■■      ■■        ■■      ■  
 ■   ■■    ■■    ■  ■■■  ■  ■■■    ■■      ■■       ■■     ■■■  
 ■■■■■     ■■    ■    ■  ■    ■    ■■      ■■      ■■        ■■ 
 ■         ■■    ■    ■  ■    ■    ■■      ■■     ■■          ■ 
 ■         ■■    ■    ■  ■    ■    ■■      ■■     ■      ■   ■■ 
 ■         ■■    ■■  ■■  ■■  ■■    ■■      ■■    ■       ■■  ■■ 
 ■         ■■      ■■■■    ■■■■    ■■      ■■    ■■■■■■   ■■■■  
*/

详细

Test #1:

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

input:

5
2
1
2
0
0
0

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 398 39...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
0

output:

0 1 2 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
2
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
0
0
0
0

output:

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

result:

ok Accepted

Test #7:

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

input:

6
1
0
0
2
2
2
2

output:

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

result:

ok Accepted

Test #8:

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

input:

7
1
2
2
0
2
0
2
0
2
2

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 7...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 321 32...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 575 57...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 550 55...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 155 15...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 372 37...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 16...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 544 54...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 96...

result:

ok Accepted

Test #26:

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

input:

984
1
1
0
1
0
1
1
1
2
1
1
2
0
2
1
2
2
1
1
1
1
2
1
2
1
2
1
0
1
0
1
2
2
1
0
0
1
1
0
0
2
1
0
0
0
0
1
0
2
1
2
0
1
0
2
1
0
2
1
0
2
0
2
2
1
0
1
1
1
1
2
0
1
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
0
0
1
1
2
1
0
2
1
1
1
0
1
1
1
1
1
1
1
2
1
0
1
0
1
2
1
2
0
0
0
1
1
1
1
2
1
1
1
1
2
1
0
1
1
0
0
0
1
2
1
0
1
0
0
1
1
2
1
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 #27:

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

input:

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

output:

0 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 208 20...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 522 52...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 693 69...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 822 82...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 690 69...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 38...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 501 50...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 422 42...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 3...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 881 88...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 896 89...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 692 69...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 663 66...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 916 91...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed