QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#598246#9432. Permutationucup-team5062#AC ✓291ms4268kbC++204.0kb2024-09-28 20:57:202024-09-28 20:57:21

Judging History

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

  • [2024-09-28 20:57:21]
  • 评测
  • 测评结果:AC
  • 用时:291ms
  • 内存:4268kb
  • [2024-09-28 20:57:20]
  • 提交

answer

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

const int DEBUG = 1;
vector<int> Target;
int Answer[1 << 19];
int Queries = 0;

int Ask(vector<int> Vec) {
	Queries += 1;
	if (DEBUG == 1) {
		printf("0");
		for (int i = 0; i < (int)Vec.size(); i++) printf(" %d", Vec[i]);
		printf("\n");
		fflush(stdout);
		int r; cin >> r;
		return r;
	}
	if (DEBUG == 2) {
		int cnt = 0;
		for (int i = 0; i < (int)Vec.size(); i++) cnt += (Target[i] == Vec[i] ? 1 : 0);
		return cnt;
	}
}

int Print(vector<int> Vec) {
	if (DEBUG == 1) {
		printf("1");
		for (int i = 0; i < (int)Vec.size(); i++) printf(" %d", Vec[i]);
		printf("\n");
		fflush(stdout);
		return 1;
	}
	if (DEBUG == 2) {
		int cnt = 0;
		for (int i = 0; i < (int)Vec.size(); i++) cnt += (Target[i] == Vec[i] ? 1 : 0);
		return (cnt == (int)Vec.size() ? 1 : 0);
	}
}

void Solve(int N, vector<int> val, vector<int> perm, vector<int> dame) {
	if (val.size() == 1) {
		Answer[perm[0]] = val[0];
		return;
	}

	// Interactive Init
	int sz = val.size();
	int mid = sz / 2;
	vector<vector<int>> Current;
	vector<vector<int>> Next;
	vector<int> Left;
	vector<int> Rigt;
	for (int idx : val) Current.push_back(vector<int>{idx});
	int remL = mid;
	int remR = sz - mid;

	// Interactive Main
	while (Current.size() >= 1) {
		for (int i = 0; i < (int)Current.size(); i += 2) {
			int cl = i;
			int cr = i + 1; if (cr == Current.size()) cr--;

			// Main Case
			if (cr - cl == 1) {
				vector<int> Vec = dame;
				for (int i =  0; i < mid; i++) Vec[perm[i]] = Current[cl][0];
				for (int i = mid; i < sz; i++) Vec[perm[i]] = Current[cr][0];
				int r = Ask(Vec);
				if (r == 2) {
					for (int idx : Current[cl]) Left.push_back(idx);
					for (int idx : Current[cr]) Rigt.push_back(idx);
					remL -= Current[cl].size();
					remR -= Current[cr].size();
				}
				if (r == 0) {
					for (int idx : Current[cr]) Left.push_back(idx);
					for (int idx : Current[cl]) Rigt.push_back(idx);
					remL -= Current[cr].size();
					remR -= Current[cl].size();
				}
				if (r == 1) {
					vector<int> New;
					for (int idx : Current[cl]) New.push_back(idx);
					for (int idx : Current[cr]) New.push_back(idx);
					Next.push_back(New);
				}
			}

			// Other Case
			if (cr - cl == 0) {
				int div2L = 0, pl = remL;
				int div2R = 0, pr = remR;
				while (pl % 2 == 0 && div2L <= 20) { div2L += 1; pl /= 2; }
				while (pr % 2 == 0 && div2R <= 20) { div2R += 1; pr /= 2; }
				if (div2L < div2R) {
					for (int idx : Current[cl]) Left.push_back(idx);
					remL -= Current[cl].size();
				}
				else {
					for (int idx : Current[cr]) Rigt.push_back(idx);
					remL -= Current[cr].size();
				}
			}
		}

		// Update
		Current = Next;
		Next.clear();
	}

	// Recursion
	vector<int> permL;
	vector<int> permR;
	for (int i =  0; i < mid; i++) permL.push_back(perm[i]);
	for (int i = mid; i < sz; i++) permR.push_back(perm[i]);
	Solve(N, Left, permL, dame);
	Solve(N, Rigt, permR, dame);
}

int main() {
	// Input
	int N; cin >> N;
	if (N == 1) {
		vector<int> Ans = {1};
		Print(Ans);
		return 0;
	}
	vector<int> perm(N, 0);
	vector<int> val(N, 0);
	for (int i = 0; i < N; i++) perm[i] = i;
	for (int i = 0; i < N; i++) val[i] = i + 1;
	for (int i = 0; i < N * 10; i++) swap(perm[rand() % N], perm[rand() % N]);

	// Decide Target
	if (DEBUG == 2) {
		Target = vector<int>(N, 0);
		for (int i = 0; i < N; i++) Target[i] = i + 1;
		for (int i = 0; i < N * 10; i++) swap(Target[rand() % N], Target[rand() % N]);
	}

	// Init
	vector<int> dame;
	while (true) {
		vector<int> perm2(N, 0);
		for (int i = 0; i < N; i++) perm2[i] = i + 1;
		for (int i = 0; i < N * 10; i++) swap(perm2[rand() % N], perm2[rand() % N]);
		int r = Ask(perm2);
		if (r == 0) { dame = perm2; break; }
	}

	// Solve
	Solve(N, val, perm, dame);

	// Output
	vector<int> Ans;
	for (int i = 0; i < N; i++) Ans.push_back(Answer[i]);
	int v = Print(Ans);
	if (DEBUG == 2) {
		cout << v << endl;
		cout << Queries << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
3
0
2
1
2
0
0

output:

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

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 282ms
memory: 4184kb

input:

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

output:

0 706 610 944 411 679 862 391 867 2 430 78 959 442 464 745 595 421 954 250 584 644 339 592 894 70 369 424 879 234 719 204 134 99 511 398 541 325 853 850 53 770 979 544 454 253 396 260 843 127 990 642 791 149 561 996 347 526 304 616 786 155 906 529 981 547 163 966 554 986 491 492 649 589 923 746 237 ...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
2
0
2

output:

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

result:

ok Accepted

Test #5:

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

input:

3
1
1
0
1
2

output:

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

result:

ok Accepted

Test #6:

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

input:

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

output:

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

result:

ok Accepted

Test #7:

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

input:

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

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 743 546 125 795 527 210 39 751 509 272 146 65 932 696 428 905 796 120 336 798 879 742 377 699 66 198 35 442 807 283 91 79 508 340 9 655 661 705 599 444 767 890 964 859 748 530 433 547 274 561 154 676 365 305 77 820 552 536 649 164 683 467 725 948 402 189 4 745 541 869 447 710 520 110 316 783 651 9...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 840 74 618 777 474 218 965 796 531 50 10 946 721 569 194 180 958 246 513 497 575 200 971 477 14 155 201 687 316 322 655 776 349 58 829 846 482 726 464 389 301 91 139 165 311 46 328 571 602 583 732 522 272 905 164 310 931 96 707 205 125 169 438 739 488 151 628 496 47 371 437 265 784 184 604 662 562...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 778 719 431 283 776 339 525 970 944 200 799 434 514 623 161 64 153 329 10 26 456 398 55 259 870 323 422 36 420 744 643 194 976 275 598 806 824 8 897 780 705 680 811 56 240 305 718 620 128 809 263 552 80 925 658 579 560 428 868 911 625 721 30 541 251 700 145 954 460 453 769 132 563 886 443 231 457 ...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 634 178 859 604 864 81 146 87 357 656 890 312 836 698 768 89 855 196 745 270 582 713 905 423 702 755 505 779 118 338 261 831 931 260 887 161 393 299 470 32 113 950 945 126 253 916 374 475 771 414 215 832 352 775 330 314 646 709 877 333 523 237 680 247 851 77 2 48 782 489 199 595 92 26 109 351 385 ...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 276 844 206 377 93 19 419 504 247 892 160 924 196 898 721 803 837 809 354 99 488 933 937 339 385 620 595 144 694 794 61 209 221 110 386 885 619 195 62 492 158 168 759 564 360 664 537 890 781 923 951 952 511 258 180 724 682 369 650 935 314 473 485 926 440 761 364 179 845 38 215 298 531 744 139 703 ...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 43 150 202 675 807 213 768 138 537 651 48 569 556 49 977 158 644 723 741 61 275 739 472 356 839 453 755 825 645 387 716 657 99 897 148 814 281 181 445 721 960 900 572 164 368 375 362 129 837 361 827 415 277 887 19 274 177 273 834 810 50 732 345 812 934 408 217 348 154 833 902 779 487 16 929 867 45...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 81 721 678 798 298 317 240 163 166 901 293 277 552 127 151 575 844 374 265 193 413 78 85 35 978 53 458 689 875 3 415 892 839 263 767 292 126 398 369 698 370 858 457 275 827 93 867 968 692 399 19 228 676 757 453 622 66 49 376 218 786 246 174 137 709 219 623 119 909 69 441 103 700 324 911 98 579 903...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 183 109 623 365 607 701 129 147 72 484 18 283 46 88 236 583 690 194 699 897 442 110 710 667 972 860 2 572 397 725 279 254 891 510 886 527 885 703 641 633 688 477 441 935 654 672 357 67 353 833 481 404 449 505 274 587 49 478 260 873 394 769 944 398 220 627 554 448 973 106 534 835 837 374 577 558 39...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 353 142 551 192 184 797 557 467 380 77 480 730 637 448 12 510 311 674 490 956 831 265 430 957 348 283 458 509 475 881 288 273 231 900 269 333 179 912 241 530 389 246 741 804 486 49 385 416 410 172 902 765 216 377 292 255 891 982 581 146 237 227 74 799 622 543 586 731 644 171 350 401 120 438 30 706...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 524 428 335 576 972 786 242 182 699 37 150 342 528 325 233 33 651 969 941 649 803 655 757 942 974 672 622 110 938 845 660 422 825 657 458 22 12 945 644 408 118 151 239 496 258 612 194 374 467 93 121 457 232 705 11 275 89 577 674 525 855 663 819 331 910 117 817 570 872 627 100 516 164 174 547 368 2...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 268ms
memory: 4196kb

input:

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

output:

0 962 778 908 836 909 447 475 453 565 921 369 256 970 98 212 745 955 902 79 517 770 186 623 307 225 871 30 334 244 426 364 579 138 576 393 753 417 929 112 493 40 973 832 265 193 520 148 338 780 124 905 333 227 645 676 923 501 21 609 398 606 75 15 179 940 494 370 771 980 185 757 87 939 924 57 958 652...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 955 136 666 718 382 473 853 467 505 911 271 64 94 348 97 488 905 641 282 775 749 693 644 768 907 759 766 829 301 777 167 804 258 430 983 366 401 800 465 426 303 490 516 950 655 855 357 45 383 595 362 941 158 340 818 133 892 194 631 102 451 240 31 350 352 139 697 184 851 59 624 692 985 620 238 647 ...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 717 504 517 982 708 881 299 664 224 520 534 649 144 325 319 941 567 56 240 454 391 178 274 303 648 95 547 167 51 68 670 39 163 530 9 712 760 112 198 671 831 859 170 305 214 608 553 550 383 950 384 8 288 189 32 425 490 346 568 737 46 555 147 62 575 130 981 827 210 102 84 871 860 573 215 754 743 514...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 277ms
memory: 4264kb

input:

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

output:

0 561 195 598 325 189 105 450 134 525 289 761 30 659 358 262 433 50 288 679 97 458 697 454 833 895 799 584 31 209 312 129 342 132 47 98 511 726 5 369 696 852 976 245 142 83 298 749 345 479 953 985 636 877 174 780 540 438 478 122 796 392 413 703 217 785 898 10 558 151 265 932 87 336 61 602 642 218 58...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 779 447 404 47 832 844 577 399 750 741 789 284 705 656 121 75 873 640 836 772 737 720 655 179 559 63 180 842 143 125 596 478 238 194 189 732 641 673 587 949 348 864 985 224 50 451 924 169 269 254 425 879 809 974 414 792 438 503 543 148 508 494 497 22 253 514 525 363 225 582 32 334 907 900 466 244 ...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 987 608 361 525 906 591 280 904 749 220 704 118 735 415 847 844 723 589 463 610 947 977 310 970 306 714 646 6 616 555 451 375 754 505 480 501 176 680 905 110 730 804 47 982 186 511 660 919 552 482 442 669 129 403 272 470 117 656 539 636 870 854 898 860 343 487 419 661 579 453 62 114 441 431 435 32...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 575 153 312 677 863 95 612 159 472 715 175 16 127 977 278 831 494 958 751 353 947 776 145 954 790 43 184 537 193 688 141 920 164 573 909 136 824 251 484 516 205 716 654 290 146 904 618 678 69 727 58 898 973 665 672 674 118 681 843 561 272 907 202 163 442 639 558 514 97 797 211 70 701 447 112 825 8...

result:

ok Accepted

Test #34:

score: 0
Accepted
time: 247ms
memory: 3920kb

input:

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

output:

0 470 525 231 365 125 747 246 962 19 147 411 843 898 389 557 630 5 897 590 241 558 102 304 574 900 637 263 468 410 589 681 569 93 641 721 775 682 153 321 700 785 913 245 869 891 302 121 186 333 268 477 506 96 138 931 401 460 363 689 521 485 220 366 723 215 661 195 612 936 258 491 779 293 598 657 392...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 663 963 807 344 492 425 407 330 200 99 646 905 243 416 693 15 840 292 576 926 564 375 473 280 766 403 142 573 513 695 351 8 743 239 103 139 44 240 930 894 544 20 363 134 353 214 108 226 373 626 163 860 448 195 335 346 752 541 62 190 423 14 545 133 561 515 920 140 736 733 323 132 10 732 495 717 790...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 915 109 477 281 687 815 252 416 90 938 99 982 316 451 274 359 219 487 301 823 13 880 471 621 904 845 104 348 422 911 444 147 651 831 615 8 580 352 218 346 19 752 475 67 292 375 800 703 403 797 177 381 361 100 4 96 543 232 492 643 501 196 890 186 184 145 205 127 480 721 313 118 14 963 415 560 50 45...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 383 214 807 819 867 60 542 486 57 501 235 421 43 720 256 364 93 287 923 458 864 65 91 749 145 676 270 150 830 134 946 367 544 602 629 891 32 889 739 273 119 589 184 927 521 983 675 603 554 304 121 567 42 537 769 482 881 714 504 240 290 423 263 175 791 658 613 518 763 229 96 552 540 314 553 975 234...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 755 99 242 214 426 995 93 691 777 720 276 625 551 66 137 273 476 567 910 475 593 812 384 536 706 334 983 888 4 385 255 336 645 717 324 833 610 569 961 907 88 903 868 391 140 159 218 410 563 944 154 897 714 299 419 773 204 284 310 65 120 64 411 173 126 636 370 694 754 272 892 851 689 480 416 465 83...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 739 579 6 53 857 975 198 400 181 719 156 427 681 101 662 497 661 794 892 235 187 822 872 467 968 566 718 5 428 233 253 232 577 179 349 812 842 11 840 58 964 420 694 819 939 631 865 728 581 702 650 887 526 712 30 891 98 962 9 39 545 368 254 914 305 470 995 461 514 912 107 573 565 983 127 284 252 98...

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 247ms
memory: 3940kb

input:

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

output:

0 832 579 167 843 761 273 902 510 139 933 929 249 991 958 117 597 60 260 844 480 806 964 168 518 490 833 626 9 944 916 797 190 214 377 257 903 767 842 775 384 298 379 747 146 793 868 562 943 918 206 931 90 711 986 537 491 426 455 27 697 600 443 94 997 331 702 594 135 744 836 37 721 63 856 859 52 184...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 24 19 246 915 907 696 345 942 535 584 39 353 546 125 325 818 364 640 519 23 736 6 302 506 384 969 917 114 599 33 330 376 766 689 855 521 13 997 316 468 856 185 166 995 774 575 64 148 164 789 771 948 947 547 422 624 797 284 292 548 84 735 294 711 655 18 641 604 679 55 241 580 776 448 452 699 509 77...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed