QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#598890#9432. Permutationucup-team3670#AC ✓345ms3816kbC++171.8kb2024-09-28 23:56:272024-09-28 23:56:29

Judging History

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

  • [2024-09-28 23:56:29]
  • 评测
  • 测评结果:AC
  • 用时:345ms
  • 内存:3816kb
  • [2024-09-28 23:56:27]
  • 提交

answer

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)

using namespace std;

mt19937 rnd(43);

vector<int> p, rk;

int getp(int a){
	return a == p[a] ? a : p[a] = getp(p[a]);
}

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return;
	if (rk[a] < rk[b]) swap(a, b);
	rk[a] += rk[b];
	p[b] = a;
}

int n;

int ask(int b, int v, int u){
	cout << "0 ";
	forn(i, n){
		if (i) cout << " ";
		if ((i >> b) & 1)
			cout << u + 1;
		else
			cout << v + 1;
	}
	cout << endl;
	int x;
	cin >> x;
	return x;
}

int main(){
	cin >> n;
	vector<int> ans(n);
	forn(b, 10){
		int cnt1 = 0;
		forn(i, n) cnt1 += (i >> b) & 1;
		int cnt0 = n - cnt1;
		
		queue<int> q;
		{
			vector<int> p(n);
			iota(p.begin(), p.end(), 0);
			shuffle(p.begin(), p.end(), rnd);
			forn(i, n) q.push(p[i]);
		}
		rk.assign(n + 2, 1);
		p.resize(n + 2);
		iota(p.begin(), p.end(), 0);
		while (q.size() > 1){
			int v = q.front();
			q.pop();
			int u = q.front();
			q.pop();
			if (rnd() & 1) swap(v, u);
			int x = ask(b, v, u);
			if (x == 1){
				unite(v, u);
				if (rk[getp(v)] > cnt0)
					unite(v, n + 1);
				else if (rk[getp(v)] > cnt1)
					unite(v, n);
				else
					q.push(v);
			}
			else{
				if (x == 0) swap(v, u);
				cnt0 -= rk[getp(v)];
				unite(v, n);
				cnt1 -= rk[getp(u)];
				unite(u, n + 1);
			}
		}
		if (q.size() == 1){
			int v = q.front();
			q.pop();
			unite(v, rk[getp(v)] == cnt1 ? n + 1 : n);
		}
		forn(i, n){
			int val = getp(i) == getp(n + 1);
			ans[i] |= val << b;
		}
	}
	vector<int> p(n);
	forn(i, n) p[ans[i]] = i;
	cout << "1";
	forn(i, n) cout << " " << p[i] + 1;
	cout << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
0
0
2
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

output:

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

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 306ms
memory: 3460kb

input:

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

output:

0 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 29...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
2
1
1
1
1
1
1
1
1
1

output:

0 2 1
0 2 2
0 2 2
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 1 1
0 2 2
1 2 1

result:

ok Accepted

Test #5:

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

input:

3
2
0
1
1
1
1
1
1
1
1

output:

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

result:

ok Accepted

Test #6:

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

input:

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

output:

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

result:

ok Accepted

Test #7:

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

input:

6
0
1
1
0
0
0
1
2
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 29...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 67...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 29...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 298ms
memory: 3584kb

input:

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

output:

0 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 67...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 316ms
memory: 3744kb

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 293ms
memory: 3528kb

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 29...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 345ms
memory: 3560kb

input:

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

output:

0 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 67...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #31:

score: 0
Accepted
time: 332ms
memory: 3460kb

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 61...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 323ms
memory: 3580kb

input:

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

output:

0 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 61...

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 323ms
memory: 3628kb

input:

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

output:

0 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 294 617 29...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 671 618 67...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed