QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742350#9432. PermutationKXGAC ✓308ms4136kbC++143.4kb2024-11-13 16:26:182024-11-13 16:26:19

Judging History

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

  • [2024-11-13 16:26:19]
  • 评测
  • 测评结果:AC
  • 用时:308ms
  • 内存:4136kb
  • [2024-11-13 16:26:18]
  • 提交

answer

#include <vector>
#include <cstdio>
#include <bits/extc++.h>
using namespace std;
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> rbtree;
int n, ans[1010];
int query(vector<int> a) {
    printf("0 ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    fflush(stdout);
    int x;
    scanf("%d", &x);
    return x;
}
int fa[1010], dir[1010];
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    fa[find(x)] = find(y);
}
void solve(int l, int r, vector<int> S, int t) {
    // printf("%d %d : ", l, r);
    // for (int x : S) {
    //     printf("%d ", x);
    // }
    // printf("\n");
    if (l == r) {
        ans[l] = S[0];
        return;
    }
    int mid = (l + r) >> 1;
    rbtree now;
    for (int i : S) {
        now.insert(i);
        dir[i] = 0;
        fa[i] = i;
    }
    while (true) {
        if (now.size() < 2) break;
        int siz = now.size();
        int xid = rand() % siz, yid = rand() % siz;
        if (xid == yid) continue;
        auto xit = now.find_by_order(xid);
        auto yit = now.find_by_order(yid);
        int x = *xit, y = *yit;
        vector<int> que;
        for (int i = 1; i <= n; i++) {
            if (i < l || i > r) {
                que.push_back(t);
            } else if (i <= mid) {
                que.push_back(x);
            } else {
                que.push_back(y);
            }
        }
        int res = query(que);
        if (res == 0) {
            dir[x] = 1;
            dir[y] = -1;
            now.erase(xit);
            now.erase(yit);
        } else if (res == 2) {
            dir[x] = -1;
            dir[y] = 1;
            now.erase(xit);
            now.erase(yit);
        } else {
            merge(x, y);
            now.erase(xit);
        }
    }
    // printf("%d %d Ok %d\n", l, r, now.size());
    int left = 0, right = 0;
    for (int i : S) {
        if (dir[i] == -1) {
            left = i;
        }
        if (dir[i] == 1) {
            right = i;
        }
    }
    if (now.size() == 1) {
        int x = *now.begin();
        if (left == 0) {
            dir[x] = -1;
        } else if (right == 0) {
            dir[x] = 1;
        } else {
            vector<int> que;
            for (int i = 1; i <= n; i++) {
                if (i < l || i > r) {
                    que.push_back(t);
                } else if (i <= mid) {
                    que.push_back(x);
                } else {
                    que.push_back(left);
                }
            }
            int res = query(que);
            if (res == 0) {
                dir[x] = 1;
            } else {
                dir[x] = -1;
            }
        }
    }
    vector<int> ls, rs;
    for (int i : S) {
        dir[i] = dir[find(i)];
        if (dir[i] == -1) {
            ls.push_back(i);
        } else {
            rs.push_back(i);
        }
    }
    solve(l, mid, ls, ls.front());
    solve(mid + 1, r, rs, rs.front());
}
int main() {
    scanf("%d", &n);
    vector<int> S;
    for (int i = 1; i <= n; i++) {
        S.push_back(i);
    }
    solve(1, n, S, 0);
    printf("1 ");
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    fflush(stdout);
    return 0;
}

详细

Test #1:

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

input:

5
1
2
0
1
2
0
2

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 384 38...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
2
1
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
1
1
0
2
2

output:

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

result:

ok Accepted

Test #7:

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

input:

6
2
2
0
1
2
0
2
1
0

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 209 20...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 152 15...

result:

ok Accepted

Test #19:

score: 0
Accepted
time: 281ms
memory: 3856kb

input:

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

output:

0 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 956 95...

result:

ok Accepted

Test #20:

score: 0
Accepted
time: 253ms
memory: 3872kb

input:

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

output:

0 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 656 65...

result:

ok Accepted

Test #21:

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

input:

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

output:

0 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 21...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 604 60...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 253ms
memory: 4096kb

input:

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

output:

0 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 830 83...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 882 88...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 748 74...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 416 41...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 859 85...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 9...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 8...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 820 82...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 311 31...

result:

ok Accepted

Test #32:

score: 0
Accepted
time: 281ms
memory: 3944kb

input:

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

output:

0 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 52...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 459 45...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 104 10...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 440 44...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 464 46...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 16...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 524 52...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 538 53...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 19...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 479 47...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed