QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604054#9432. Permutationucup-team4906AC ✓289ms4260kbC++143.5kb2024-10-01 22:35:582024-10-01 22:35:59

Judging History

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

  • [2024-10-01 22:35:59]
  • 评测
  • 测评结果:AC
  • 用时:289ms
  • 内存:4260kb
  • [2024-10-01 22:35:58]
  • 提交

answer

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

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define Sz(x) (int)(x).size()
#define bit(x) (1ll << (x))
using ll = long long;
using db = double;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vd = vector<db>;
mt19937 mrand(time(0));

int n;
int query(vi v)
{
	cout << 0 << " ";
	for (int i = 1; i <= n; i++)
		cout << v[i] << " ";
	cout << endl;
	int res;
	cin >> res;
	return res;	
}

void solve(void)
{
	cin >> n;

	vi a(n + 2);
	for (int i = 1; i <= n; i++)
		a[i] = i;

	vi ans(n + 2), que(n + 2);
	function<void(int, int)> dfs = [&](int l, int r)
	{
		if (l == r)
		{
			ans[l] = a[l];
			return;
		}

		int mid = (l + r) / 2;
		vi vis(n + 2);
		vii e(n + 2);
		vi fa(n + 2);
		for (int i = l; i <= r; i++)
		{
			fa[a[i]] = a[i];
			e[a[i]].pb(a[i]);
		}

		function<int(int)> find = [&](int u)
		{
			if (fa[u] == u) return u;
			return fa[u] = find(fa[u]);
		};

		while (true)
		{
			vi v;
			for (int i = l; i <= r; i++)
			{
				int f = find(a[i]);
				if (f == a[i] && !vis[f])
				{
					// cerr << f << " ";
					v.pb(f);
				}
			}
			// cerr << "\n";

			if (Sz(v) == 0)
				break;
			else if (Sz(v) == 1)
			{
				int cl = 0;
				for (int i = l; i <= r; i++)
					if (vis[a[i]] == -1) cl++;

				int u = v[0];

				if (cl != mid - l + 1)
				{
					assert(cl + Sz(e[u]) == mid - l + 1);
					for (auto x : e[u])
					{
						assert(vis[x] == 0);
						vis[x] = -1;
					}
				}
				else
					for (auto x : e[u])
					{
						assert(vis[x] == 0);
						vis[x] = 1;
					}
				break;
			}
			else
			{
				random_shuffle(all(v));
				int m = Sz(v);
				for (int i = 0; i < m; i += 2)
				{
					int x = v[i], y = v[(i + 1) % m];
					for (int j = 1; j <= mid; j++)
						que[j] = x;
					for (int j = mid + 1; j <= n; j++)
						que[j] = y;

					int res = query(que);
					if (res == 2)
					{
						for (auto a : e[x])
							vis[a] = -1;
						for (auto a : e[y])
							vis[a] = 1;
					}
					else if (res == 0)
					{
						swap(x, y);
						for (auto a : e[x])
							vis[a] = -1;
						for (auto a : e[y])
							vis[a] = 1;
					}
					else
					{
						// cerr << x << " " << y << " " << vis[y] << "\n";
						if (vis[x])
						{
							for (auto a : e[y])
								vis[a] = vis[x];
							
						}
						else if (vis[y])
						{
							for (auto a : e[x])
							{
								// cerr << a << "\n";
								vis[a] = vis[y];							
							}
						}
						else
						{
							fa[y] = x;
							for (auto a : e[y])
								e[x].pb(a);
							e[y].clear();
						}
					}
				}
			}
		}

		// cerr << "YES\n";
		vi vl, vr;
		int pl = l, pr = mid + 1;
		for (int i = l; i <= r; i++)
		{
			assert(vis[a[i]]);
			if (vis[a[i]] == -1)
				vl.pb(a[i]);
			else
				vr.pb(a[i]);
		}

		for (auto x : vl)
			a[pl++] = x;
		for (auto x : vr)
			a[pr++] = x;
		
		dfs(l, mid);
		dfs(mid + 1, r);
	};

	dfs(1, n);

	cout << 1 << " ";
	for (int i = 1; i <= n; i++)
		cout << ans[i] << " ";
	cout << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// cout << fixed << setprecision(10);

	int T = 1;
	// cin >> T;
	for (int i = 1; i <= T; i++)
	solve();

	return 0;
}

詳細信息

Test #1:

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

input:

5
0
1
1
0
2
0
0

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
0

output:

0 1 2 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
1
0
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
0
0
2
0

output:

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

result:

ok Accepted

Test #7:

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

input:

6
0
1
1
0
2
1
2
2
1
2

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 222ms
memory: 4252kb

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 241ms
memory: 4048kb

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 245ms
memory: 4020kb

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed