QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#599489#9432. Permutationucup-team3099#AC ✓291ms3940kbC++203.9kb2024-09-29 05:37:142024-09-29 05:37:15

Judging History

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

  • [2024-09-29 05:37:15]
  • 评测
  • 测评结果:AC
  • 用时:291ms
  • 内存:3940kb
  • [2024-09-29 05:37:14]
  • 提交

answer

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

bool DEBUG = false;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> pos(n), que(n), ans(n);
    int tot_que = 0;
    iota(ans.begin(), ans.end(), 0); // shuffle(ans.begin(), ans.end(), rng);
    auto ask = [&]() {
        if (tot_que++ >= 6666) {
            if (DEBUG) {
                // assert(false);
            } else {
                // troll
                for (int i = 0; ; i++) {
                    tot_que++;
                }
            }
        }
        if (!DEBUG) {
            cout << 0;
            for (int v : que) {
                cout << " " << v + 1;
            }
            cout << endl;
            int ret; cin >> ret; return ret;
        } else {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cnt += ans[i] == que[i];
            }
            return cnt;
        }
    };
    auto check = [&](int u, int v, int bit) {
        for (int j = 0; j < n; j++) {
            que[j] = (j >> bit & 1) ? u : v;
        }
        return ask();
    };
    for (int lg = (n == 1 ? -1 : __lg(n - 1)); lg >= 0; lg--) {
        vector<int> cur(n, -1);
        vector<list<int>> vals(n);
        if (lg > 0) {
            for (int i = 0; i < n; i++) {
                vals[i].push_back(i);
            }
            shuffle(vals.begin(), vals.end(), rng);
        } else {
            vector<vector<int>> buc(n);
            for (int i = 0; i < n; i++) {
                buc[pos[i]].push_back(i);
            }
            for (int i = 0, cnt = 0; i < n; i++) {
                for (int v : buc[i]) {
                    vals[cnt++].push_back(v);
                }
            }
        }
        while (vals.size() >= 2) {
            vector<list<int>> nxt;
            for (int i = 0; i < vals.size(); i += 2) {
                if (i + 1 < vals.size()) {
                    int u = vals[i].front(), v = vals[i + 1].front();
                    int ret = check(u, v, lg);
                    if (ret % 2 == 0) {
                        // u is 0, v = 1
                        {
                            for (int x : vals[i]) {
                                cur[x] = ret / 2;
                            }
                        }
                        {
                            for (int x : vals[i + 1]) {
                                cur[x] = 1 - ret / 2;
                            }
                        }
                    } else {
                        vals[i].splice(vals[i].end(), vals[i + 1]);
                        nxt.push_back(vals[i]);
                    }
                } else {
                    nxt.push_back(vals[i]);
                }
            }
            vals = move(nxt);
        }
        if (vals.size() == 1) {
            int cnt_half_1 = 0, tot_half_1 = 0;
            for (int i = 0; i < n; i++) {
                if (cur[i] == 1) {
                    cnt_half_1++;
                }
                if (i >> lg & 1) {
                    tot_half_1++;
                }
            }
            for (int x : vals[0]) {
                cur[x] = (cnt_half_1 != tot_half_1);
            }
        }
        for (int i = 0; i < n; i++) {
            pos[i] |= (cur[i] << lg);
        }
        cerr << tot_que << '\n';
    }
    vector<int> per(n);
    for (int i = 0; i < n; i++) {
        per[pos[i]] = i;
    }
    if (!DEBUG) {
        cout << 1;
        for (int i = 0; i < n; i++) {
            cout << " " << per[i] + 1;
        }
        cout << endl;
    } else {
        for (int i = 0; i < n; i++) {
            if (ans[i] != per[i]) {
                cout << "WA!\n";
                return 0;
            }
        }
        cout << "tot query: " << tot_que << '\n';
    }
}
// 3 1 5 2 4

详细

Test #1:

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

input:

5
1
2
1
1
1
0
0
2

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 11...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1
1 2 1

result:

ok Accepted

Test #5:

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

input:

3
1
0
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
1
1
0
0
2

output:

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

result:

ok Accepted

Test #7:

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

input:

6
2
2
1
1
0
0
0
2
2

output:

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

result:

ok Accepted

Test #8:

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

input:

7
0
2
2
0
2
1
0
0
2
2

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 355 35...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 91 9...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 683 68...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 964 96...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 399 39...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 434 43...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 20...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 231 23...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 629 62...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 333 33...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 76 7...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 270 27...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 278ms
memory: 3936kb

input:

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

output:

0 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 965 96...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 322 32...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 578 57...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 727 72...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 990 99...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 466 46...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 631 63...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 450 45...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 901 90...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 646 64...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 970 97...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 954 95...

result:

ok Accepted

Test #41:

score: 0
Accepted
time: 246ms
memory: 3932kb

input:

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

output:

0 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 502 50...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed