QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#597395#9432. Permutationucup-team3646#AC ✓323ms3908kbC++174.4kb2024-09-28 17:44:102024-09-28 17:44:11

Judging History

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

  • [2024-09-28 17:44:11]
  • 评测
  • 测评结果:AC
  • 用时:323ms
  • 内存:3908kb
  • [2024-09-28 17:44:10]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>

using namespace std;

class UnionFind {
public:
    vector<int> parents;
    int group_count;

    UnionFind(int n) : parents(n, -1), group_count(n) {}

    int find(int x) {
        if (parents[x] < 0)
            return x;
        else
            return parents[x] = find(parents[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;

        if (parents[x] > parents[y]) swap(x, y);

        parents[x] += parents[y];
        parents[y] = x;
        group_count--;
    }

    int size(int x) {
        return -parents[find(x)];
    }
};

int LOCAL = 0;
int N = 0;
int cnt = 0;
vector<int> ans;

int ask(const vector<int>& p) {
    cnt++;
    if (LOCAL) {
        for (int i : p)
            assert(1 <= i && i <= N);
        int same = 0;
        for (int i = 0; i < N; ++i)
            if (p[i] == ans[i])
                same++;
        return same;
    } else {
        cout << 0;
        for (int i : p)
            cout << " " << i;
        cout << endl;
        int same;
        cin >> same;
        return same;
    }
}

void answer(const vector<int>& p) {
    if (LOCAL) {
        assert(ans == p);
        cout << "cnt " << cnt << endl;
    } else {
        cout << 1;
        for (int i : p)
            cout << " " << i;
        cout << endl;
    }
}

void calc(int l, int r, vector<int>& rem, vector<int>& dummy, vector<int>& tmp) {
    if (rem.empty()) return;
    if (rem.size() == 1) {
        tmp[l] = rem[0];
        return;
    }

    vector<int> nL, nR;
    int mid = (l + r) / 2;

    vector<int> todo;
    while (rem.size() > 1) {
        todo.push_back(rem.back()); rem.pop_back();
        todo.push_back(rem.back()); rem.pop_back();
    }

    int sz = todo.size();
    UnionFind uf(sz);
    vector<int> seen(sz, -1);
    vector<int> Q = todo;

    todo.resize(sz);
    iota(todo.begin(), todo.end(), 0);

    while (!todo.empty()) {
        if (todo.size() >= 2) {
            int x = todo.back(); todo.pop_back();
            int y = todo.back(); todo.pop_back();
            vector<int> p = dummy;
            for (int i = l; i < mid; ++i) p[i] = Q[x];
            for (int i = mid; i < r; ++i) p[i] = Q[y];
            int s = ask(p);
            if (s == 0) {
                seen[x] = 1;
                seen[y] = 0;
            } else if (s == 2) {
                seen[x] = 0;
                seen[y] = 1;
            } else if (s == 1) {
                uf.unite(x, y);
                todo.push_back(uf.find(x));
            }
        } else {
            int x = todo.back(); todo.pop_back();
            vector<int> p = dummy;
            for (int i = l; i < mid; ++i) p[i] = Q[x];
            int s = ask(p);
            seen[x] = (s == 1 ? 0 : 1);
        }
    }

    for (int i = 0; i < sz; ++i) {
        if (seen[uf.find(i)] == 0) nL.push_back(Q[i]);
        else nR.push_back(Q[i]);
    }

    if (!rem.empty()) {
        int val = rem.back(); rem.pop_back();
        if (mid - l != nL.size())
            nL.push_back(val);
        else
            nR.push_back(val);
    }

    calc(l, mid, nL, dummy, tmp);
    calc(mid, r, nR, dummy, tmp);
}

void solve() {
    if (N == 1) {
        answer({1});
        return;
    }
    if (N == 2) {
        int s = ask({1, 2});
        if (s == 2)
            answer({1, 2});
        else
            answer({2, 1});
        return;
    }

    vector<int> dummy(N);
    iota(dummy.begin(), dummy.end(), 1);
    vector<int> p;
    while (true) {
        p = dummy;
        shuffle(p.begin(), p.end(), mt19937(random_device()()));
        int s = ask(p);
        if (s == 0) {
            dummy = p;
            break;
        }
    }

    vector<int> tmp(N, -1);
    vector<int> cand(N);
    iota(cand.begin(), cand.end(), 1);
    shuffle(cand.begin(), cand.end(), mt19937(random_device()()));

    calc(0, N, cand, dummy, tmp);
    answer(tmp);
}

int main() {
    while (true) {
        if (LOCAL) {
            N = 1000;
            ans.resize(N);
            iota(ans.begin(), ans.end(), 1);
            shuffle(ans.begin(), ans.end(), mt19937(random_device()()));
        } else {
            cin >> N;
        }

        solve();

        if (!LOCAL) exit(0);
        cnt = 0;
    }
}

详细

Test #1:

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

input:

5
0
2
2
0
1
0
0

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 82 464 449 275 90 971 352 96 753 72 175 119 106 28 734 612 882 258 527 456 217 811 812 911 804 443 889 518 756 721 825 611 271 326 864 537 655 641 97 962 291 887 492 159 659 803 62 338 740 823 934 220 17 816 776 173 202 201 914 551 21 835 457 245 297 148 374 164 670 310 233 711 226 1000 480 137 96...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
0

output:

0 1 2
1 2 1

result:

ok Accepted

Test #5:

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

input:

3
1
1
1
1
0
0
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
0
2
2
2
0

output:

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

result:

ok Accepted

Test #7:

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

input:

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

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 287ms
memory: 3708kb

input:

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

output:

0 694 522 527 196 788 922 30 764 253 931 271 90 408 580 541 534 753 454 973 681 217 615 890 63 548 819 298 717 96 285 356 242 20 760 168 232 569 892 874 698 787 14 94 45 772 309 804 832 628 739 710 672 736 235 965 677 478 15 942 246 47 202 162 166 905 797 904 332 716 741 345 77 207 229 488 144 60 82...

result:

ok Accepted

Test #18:

score: 0
Accepted
time: 307ms
memory: 3704kb

input:

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

output:

0 956 276 177 184 403 320 99 398 756 613 789 665 530 115 262 110 29 503 17 901 147 425 794 4 784 416 572 15 72 511 586 606 911 692 664 140 22 192 166 716 864 449 668 891 569 461 674 60 649 786 186 653 380 618 245 238 564 807 145 706 869 699 453 588 666 505 636 28 142 647 118 167 557 764 738 112 367 ...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 655 672 275 457 217 798 325 261 573 158 362 260 248 344 380 689 910 266 864 186 899 489 307 770 812 67 777 818 697 928 558 63 12 23 886 542 618 469 420 113 519 105 363 757 337 510 381 153 605 318 580 402 793 709 136 410 710 884 52 328 311 257 125 675 526 68 171 815 739 468 973 965 395 455 453 285 ...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 548 702 890 659 23 135 713 682 313 237 478 875 503 831 873 805 15 36 924 329 685 232 7 691 390 217 750 509 761 614 528 525 523 49 384 470 219 869 424 254 6 598 104 442 506 857 399 471 539 85 406 34 121 21 734 630 803 30 286 225 1 822 884 833 194 944 837 777 72 774 967 485 334 646 362 197 635 606 9...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 760 974 223 727 528 469 6 2 115 662 118 160 26 390 821 979 130 153 353 524 892 601 50 155 676 626 106 653 663 635 798 194 939 36 23 956 302 815 445 938 453 618 423 454 325 168 350 811 545 103 680 534 272 777 328 333 836 366 530 702 37 924 449 566 650 129 485 55 522 691 179 447 562 81 818 242 227 4...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 732 345 52 745 699 776 11 579 815 686 890 548 313 595 328 335 869 343 812 656 220 274 594 698 330 520 96 843 76 367 281 334 874 674 821 364 56 760 877 665 65 122 452 303 308 293 773 294 853 668 765 21 528 772 523 173 79 469 206 4 589 892 742 219 707 547 393 954 889 207 643 660 331 858 120 417 102 ...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 283ms
memory: 3696kb

input:

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

output:

0 183 826 857 935 5 309 920 548 36 784 1 740 319 951 715 485 110 878 341 792 840 496 939 741 783 382 664 942 69 630 641 484 67 505 812 174 604 405 74 96 534 186 929 371 530 973 868 739 272 551 432 354 256 468 953 216 317 4 582 52 501 25 193 825 365 531 726 359 226 218 493 902 552 205 138 124 692 403...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 759 611 798 854 300 628 456 529 434 788 136 293 982 715 931 237 117 678 852 162 516 334 17 382 426 836 578 577 587 168 885 806 148 350 301 890 21 803 853 664 415 677 429 165 413 584 478 563 284 532 141 178 699 373 470 111 918 676 975 706 841 775 842 343 649 273 731 8 351 183 219 267 35 828 914 721...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 884 72 110 245 957 436 557 330 88 784 45 112 879 171 948 409 766 312 286 841 238 775 900 199 67 593 234 866 183 382 826 815 132 392 20 562 58 263 651 144 748 916 204 327 253 395 56 714 795 89 504 820 701 817 169 157 941 329 814 810 221 377 643 565 910 102 863 828 666 302 516 927 188 81 198 389 21 ...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 302ms
memory: 3704kb

input:

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

output:

0 542 264 610 681 399 232 973 430 274 88 400 675 381 109 862 442 293 39 583 733 934 316 479 403 329 292 596 484 564 589 916 167 104 362 609 475 8 68 901 441 14 315 93 97 178 657 974 691 562 47 943 701 257 647 712 112 148 100 903 945 302 215 246 594 327 763 211 266 905 314 343 503 803 631 278 876 32 ...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 92 811 392 350 368 680 480 55 707 377 410 312 650 476 889 620 623 143 493 240 321 903 919 104 180 767 548 362 918 254 611 52 208 472 518 702 551 304 202 909 670 744 424 453 390 929 365 582 618 669 61 629 662 374 657 625 388 817 318 666 228 22 70 341 599 332 601 791 57 958 376 984 346 979 406 546 7...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 959 769 481 361 827 344 539 957 837 916 825 1 668 462 240 935 41 49 880 459 233 969 821 796 674 604 318 383 646 350 476 236 743 660 834 941 943 956 162 567 814 786 835 644 702 556 135 542 148 339 648 311 435 951 253 746 562 228 504 210 884 246 428 93 427 574 51 776 222 24 96 675 788 576 466 100 85...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 128 55 854 783 937 375 931 279 602 367 846 328 297 549 2 643 310 247 38 748 599 672 355 682 662 398 736 314 951 76 312 377 195 418 7 203 612 268 5 909 334 479 292 786 96 12 254 912 132 873 177 573 217 470 536 250 143 42 6 961 326 304 868 197 784 220 569 263 65 112 634 857 434 987 658 721 688 849 2...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 380 772 102 953 96 673 285 407 234 572 275 288 692 112 607 409 143 133 623 58 630 448 282 147 552 319 685 536 628 862 657 172 881 140 417 933 499 395 617 501 859 279 902 300 906 423 433 783 918 399 201 290 522 358 84 864 669 896 6 764 322 495 887 227 62 210 914 836 912 274 644 367 316 148 908 854 ...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 474 12 318 375 644 728 970 693 747 208 360 527 695 961 758 501 564 638 498 254 489 925 563 325 356 308 978 763 363 507 875 986 29 397 250 204 269 584 606 323 855 650 561 965 379 851 723 954 541 307 571 76 857 274 775 122 903 272 216 802 1 418 792 365 97 162 463 955 895 193 909 110 142 166 394 628 ...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 951 288 68 49 134 143 365 141 72 709 243 158 260 88 59 828 601 862 954 909 420 126 36 359 407 962 761 858 841 568 287 788 206 571 615 564 782 159 686 216 699 121 797 742 861 524 450 736 500 432 398 170 968 919 236 165 792 314 838 789 694 517 311 731 791 482 685 956 178 201 257 335 662 71 503 146 2...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 341 599 745 832 851 369 791 364 815 739 514 254 345 356 955 638 202 811 541 88 352 846 670 476 722 875 80 517 78 839 316 90 725 386 174 691 298 493 106 395 945 26 269 13 643 549 329 594 795 658 410 450 622 619 958 640 512 28 118 580 748 810 438 947 515 205 949 223 427 374 387 798 327 384 446 639 2...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 885 473 325 717 407 403 111 642 624 984 699 843 343 430 269 412 263 493 970 887 749 818 453 400 541 389 167 175 296 793 381 867 627 499 326 147 232 57 183 106 618 186 896 254 339 53 889 90 697 614 315 435 820 676 746 901 748 982 309 240 771 985 330 408 55 814 941 744 33 914 468 696 197 686 898 934...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 915 893 394 428 636 137 960 616 41 141 993 206 849 558 208 443 25 745 920 244 833 349 11 666 460 579 725 463 55 824 794 888 943 588 3 724 581 58 196 81 120 451 954 972 828 580 345 675 569 948 688 959 566 111 14 283 9 415 623 52 397 734 339 118 435 736 769 937 424 218 557 854 822 618 663 319 806 61...

result:

ok Accepted

Test #36:

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

input:

994
3
4
0
1
1
1
0
0
2
1
1
0
2
2
1
1
0
1
1
2
1
1
0
0
1
2
1
1
1
2
0
2
2
2
2
1
0
2
0
0
1
1
2
2
0
2
1
1
2
2
0
1
1
1
1
1
2
1
1
1
2
2
1
2
1
1
1
2
2
1
1
1
1
1
0
2
1
0
2
1
1
0
2
1
1
1
2
2
1
0
1
1
2
1
1
2
0
1
1
1
1
1
2
1
0
1
1
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
2
1
2
1
2
1
2
2
1
0
1
1
1
0
0
2
1
1
1
2
0
2
1
1
2
0
...

output:

0 963 340 807 499 574 36 754 352 578 694 797 677 118 149 69 364 739 376 616 552 804 814 221 607 969 448 274 275 393 683 363 250 831 851 915 349 188 31 492 79 753 955 401 983 10 89 560 468 659 316 359 538 121 520 899 950 147 876 109 303 707 164 150 70 706 729 984 927 467 933 566 357 146 277 231 367 2...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 916 138 804 395 335 823 943 577 979 822 73 704 730 697 440 782 151 936 563 847 703 691 348 363 910 56 134 461 492 589 874 108 546 12 708 470 133 64 780 850 625 191 652 991 797 185 677 21 256 528 705 727 653 813 905 865 879 923 318 896 946 389 274 31 612 515 757 445 234 803 136 622 505 275 868 366 ...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 610 829 791 134 344 425 776 212 112 311 779 230 36 653 253 617 333 785 782 906 91 379 573 821 705 219 854 52 945 895 360 687 587 317 95 49 681 639 258 387 463 229 329 866 93 256 27 183 252 832 615 775 560 82 293 195 205 527 734 795 848 773 841 751 158 708 439 813 840 281 322 752 210 397 268 461 41...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 57 110 475 451 783 344 209 907 440 9 104 522 929 670 970 735 116 811 121 900 385 799 356 812 508 5 27 277 447 555 849 995 760 92 154 792 310 768 686 455 964 843 931 872 65 639 106 543 13 289 803 826 464 912 902 352 510 112 281 431 22 547 67 256 125 741 282 951 190 233 704 784 985 428 417 34 961 85...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 995 351 81 842 29 407 325 72 269 399 123 833 671 499 364 244 469 973 589 864 733 845 826 906 615 555 909 900 103 803 586 552 663 811 855 992 279 509 268 685 621 573 551 340 426 303 321 140 118 391 979 463 27 252 927 379 904 109 387 330 938 44 457 15 791 779 831 584 237 133 1 488 574 627 815 863 54...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 135 868 530 811 935 291 484 873 849 194 372 730 973 356 315 267 30 13 230 645 507 809 854 559 788 605 689 540 757 914 980 440 800 418 344 488 402 555 985 560 954 704 637 466 663 362 167 250 151 902 648 921 78 658 950 832 104 442 33 651 443 899 83 492 953 12 114 57 946 977 679 318 991 708 254 3 427...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed