QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610757#9432. PermutationKevin5307AC ✓280ms3872kbC++232.6kb2024-10-04 17:17:332024-10-04 17:18:30

Judging History

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

  • [2024-10-04 17:18:30]
  • 评测
  • 测评结果:AC
  • 用时:280ms
  • 内存:3872kb
  • [2024-10-04 17:17:33]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
mt19937_64 rng(114514);
int ans[1010];
int n;
int p[1010];
int tot;
int query(vector<int> vec)
{
	tot++;
	int ret=0;
	for(int i=1;i<=n;i++)
		if(p[i]==vec[i-1])
			ret++;
	return ret;
}
void solve(int l,int r,vector<int> vec)
{
	if(l==r)
	{
		ans[l]=vec[0];
		return ;
	}
	shuffle(ALL(vec),rng);
	int mid=(l+r)/2;
	vector<int> vl,vr;
	int cur=-1;
	vector<int> temp;
	int ind=0;
	for(int i=1;i<sz(vec);i++)
	{
		if(sz(vl)==mid-l+1)
		{
			for(int j=i;j<sz(vec);j++)
				vr.pb(vec[j]);
			break;
		}
		if(sz(vr)==r-mid)
		{
			for(int j=i;j<sz(vec);j++)
				vl.pb(vec[j]);
			break;
		}
		if(ind==-1)
		{
			ind=i;
			continue;
		}
		vector<int> vq;
		for(int j=1;j<l;j++)
			vq.pb(vec[ind]);
		for(int j=l;j<=mid;j++)
			vq.pb(vec[ind]);
		for(int j=mid+1;j<=r;j++)
			vq.pb(vec[i]);
		for(int j=r+1;j<=n;j++)
			vq.pb(vec[ind]);
		cout<<"0";
		for(auto x:vq)
			cout<<" "<<x;
		cout<<endl;
		int ans;
		cin>>ans;
		// ans=query(vq);
		if(ans==2)
		{
			if(cur==-1)
			{
				vl.pb(vec[ind]);
				for(auto x:temp)
					vl.pb(x);
				temp.clear();
			}
			vr.pb(vec[i]);
			cur=-1;
			ind=-1;
		}
		else if(!ans)
		{
			if(cur==-1)
			{
				vr.pb(vec[ind]);
				for(auto x:temp)
					vr.pb(x);
				temp.clear();
			}
			vl.pb(vec[i]);
			cur=-1;
			ind=-1;
		}
		else
		{
			if(cur==-1)
			{
				temp.pb(vec[i]);
				continue;
			}
			if(cur==0) vl.pb(vec[i]);
			if(cur==1) vr.pb(vec[i]);
		}
	}
	solve(l,mid,vl);
	solve(mid+1,r,vr);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	vector<int> vec;
	for(int i=1;i<=n;i++)
		vec.pb(i);
	// for(int i=1;i<=n;i++)
	// 	p[i]=i;
	// shuffle(p+1,p+n+1,rng);
	// solve(1,n,vec);
	// for(int i=1;i<=n;i++)
	// 	assert(ans[i]==p[i]);
	// cout<<tot<<endl;
	// return 0;
	solve(1,n,vec);
	cout<<"1 ";
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

input:

5
2
1
2
0
2
2

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
1
2
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
2
0
2

output:

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

result:

ok Accepted

Test #7:

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

input:

6
2
0
2
0
0
1
2
0

output:

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

result:

ok Accepted

Test #8:

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

input:

7
0
0
0
2
0
0
2
2
0

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

0 3 3 3 3 7 7 7 7
0 3 3 3 3 6 6 6 6
0 2 2 2 2 4 4 4 4
0 5 5 5 5 8 8 8 8
0 5 5 5 5 1 1 1 1
0 3 3 7 7 3 3 3 3
0 3 3 2 2 3 3 3 3
0 7 3 7 7 7 7 7 7
0 1 1 1 2 1 1 1 1
0 6 6 6 6 6 6 8 8
0 5 5 5 5 5 5 4 4
0 5 5 5 5 5 6 5 5
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: 3800kb

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

0 3 3 3 3 3 3 7 7 7 7 7 7
0 3 3 3 3 3 3 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 5 5 5 5 5 5
0 12 12 12 12 12 12 1 1 1 1 1 1
0 8 8 8 8 8 8 9 9 9 9 9 9
0 11 11 11 11 11 11 10 10 10 10 10 10
0 5 5 5 1 1 1 5 5 5 5 5 5
0 5 5 5 10 10 10 5 5 5 5 5 5
0 3 3 3 9 9 9 3 3 3 3 3 3
0 10 10 7 10 10 10 ...

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 251ms
memory: 3568kb

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 235ms
memory: 3660kb

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 251ms
memory: 3656kb

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 562 56...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 242ms
memory: 3564kb

input:

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

output:

0 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 305 30...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed