QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#608741#9432. Permutationreal_sigma_team#AC ✓232ms3924kbC++234.9kb2024-10-04 02:04:052024-10-04 02:04:07

Judging History

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

  • [2024-10-04 02:04:07]
  • 评测
  • 测评结果:AC
  • 用时:232ms
  • 内存:3924kb
  • [2024-10-04 02:04:05]
  • 提交

answer

#include <bits/stdc++.h>
#include <immintrin.h>

using namespace std;

using ll = long long;
using ld = long double;
# define x first
# define y second
# define all(x) x.begin(), x.end()
# define rall(x) x.rbegin(), x.rend()

mt19937 mt(123);

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    init();
    cout << fixed << setprecision(10);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

void init() {}

constexpr int N = 1010;
int dsu[N], ans[N], n, have = 0;

int get(int x) {
    return dsu[x] == x ? x : dsu[x] = get(dsu[x]);
}

void merge(int x, int y) {
    dsu[get(y)] = get(x);
}

int ask() {
    cout << "0 ";
    for (int i = 0; i < n; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
    int res;
    cin >> res;
    return res - have;
}

void rec(int l, int r, vector<int> val) {
    vector<int> oval = val;
    if (l == r) {
        ans[l] = val[0];
        have++;
        return;
    }
    for (int i = 0; i < oval.size(); i++) {
        dsu[oval[i]] = oval[i];
    }
    int mid = (r + l) / 2;
    vector<int> vall, valr;
    while (vall.size() + valr.size() < r - l + 1) {
        vector<int> ost;
        shuffle(all(val), mt);
        while (!val.empty()) {
            if (val.size() == 1 && ost.empty()) {
                if (vall.empty()) {
                    int nt = valr[0];
                    for (int i = l; i <= mid; i++) {
                        ans[i] = nt;
                    }
                    for (int i = mid + 1; i <= r; i++) {
                        ans[i] = val.back();
                    }
                    if (ask()) {
                        valr.push_back(val.back());
                    } else {
                        vall.push_back(val.back());
                    }
                    val.pop_back();
                } else {
                    int nt = vall[0];
                    for (int i = mid + 1; i <= r; i++) {
                        ans[i] = nt;
                    }
                    for (int i = l; i <= mid; i++) {
                        ans[i] = val.back();
                    }
                    if (ask()) {
                        for (int i = 0; i < oval.size(); i++) {
                            if (get(oval[i]) == get(val.back())) {
                                vall.push_back(oval[i]);
                            }
                        }
                    } else {
                        for (int i = 0; i < oval.size(); i++) {
                            if (get(oval[i]) == get(val.back())) {
                                valr.push_back(oval[i]);
                            }
                        }
                    }
                    val.pop_back();
                }
            } else {
                if (val.size() == 1) {
                    val.push_back(ost.back());
                    ost.pop_back();
                }
                int ff = val.back();
                val.pop_back();
                int ss = val.back();
                val.pop_back();
                for (int i = l; i <= mid; i++) {
                    ans[i] = ff;
                }
                for (int i = mid + 1; i <= r; i++) {
                    ans[i] = ss;
                }
                int res = ask();
                if (res == 2) {
                    for (int i = 0; i < oval.size(); i++) {
                        if (get(oval[i]) == get(ff)) {
                            vall.push_back(oval[i]);
                        }
                    }
                    for (int i = 0; i < oval.size(); i++) {
                        if (get(oval[i]) == get(ss)) {
                            valr.push_back(oval[i]);
                        }
                    }
                } else if (res == 0) {
                    for (int i = 0; i < oval.size(); i++) {
                        if (get(oval[i]) == get(ss)) {
                            vall.push_back(oval[i]);
                        }
                    }
                    for (int i = 0; i < oval.size(); i++) {
                        if (get(oval[i]) == get(ff)) {
                            valr.push_back(oval[i]);
                        }
                    }
                } else {
                    merge(ff, ss);
                    ost.push_back(ff);
                }
            }
        }
        swap(val, ost);
    }
    for (int i = mid + 1; i <= r; i++) {
        ans[i] = vall[0];
    }
    rec(l, mid, vall);
    rec(mid + 1, r, valr);
}

void solve() {
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        v[i] = i + 1;
    }
    rec(0, n - 1, v);
    cout << "1 ";
    for (int i = 0; i < n; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
0
1
2
0
1
0
3

output:

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

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 220ms
memory: 3892kb

input:

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

output:

0 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 176 17...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
0
1
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
0
0
2
2

output:

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

result:

ok Accepted

Test #7:

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

input:

6
1
1
0
2
1
2
2
3
4
3

output:

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

result:

ok Accepted

Test #8:

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

input:

7
1
0
1
0
1
0
0
2
4
4
5
4

output:

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

result:

ok Accepted

Test #9:

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

input:

8
1
1
1
1
1
1
0
0
0
2
2
4
6
6
8

output:

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

result:

ok Accepted

Test #10:

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

input:

9
0
1
0
1
0
1
1
2
2
2
1
0
3
7
5
7
7

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

13
2
1
1
0
1
1
0
2
1
2
1
0
2
1
1
0
2
4
4
5
4
9
7
7
8
9
7
10
11
10

output:

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

result:

ok Accepted

Test #15:

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

input:

14
2
1
1
2
1
1
0
1
1
0
0
1
2
2
0
2
0
4
5
6
4
8
8
8
8
9
8
9
9
7
11
11
12
11

output:

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

result:

ok Accepted

Test #16:

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

input:

15
2
2
1
1
0
0
2
0
1
0
0
2
0
2
2
2
2
5
5
4
4
6
10
10
8
9
10
8
8
10
14
13
14

output:

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

result:

ok Accepted

Test #17:

score: 0
Accepted
time: 188ms
memory: 3668kb

input:

975
1
2
1
2
2
1
1
2
2
1
2
1
1
0
1
2
1
0
1
1
0
0
1
2
0
1
1
1
1
1
1
1
1
0
2
2
1
0
1
0
1
2
1
2
0
0
1
2
0
1
1
1
1
1
2
1
2
1
2
0
0
2
2
1
1
0
0
0
1
0
2
1
0
1
1
1
1
2
2
0
2
0
1
2
1
1
1
2
1
2
2
0
0
2
1
0
1
0
0
0
1
0
1
1
1
1
1
0
2
1
1
2
0
1
1
0
1
1
2
1
1
1
2
1
2
1
1
1
1
1
1
1
1
2
2
1
0
2
1
0
1
1
1
2
1
1
0
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 #18:

score: 0
Accepted
time: 208ms
memory: 3724kb

input:

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

output:

0 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 945 94...

result:

ok Accepted

Test #19:

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

input:

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

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 #20:

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

input:

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

output:

0 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 13...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 190ms
memory: 3688kb

input:

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

output:

0 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 476 47...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 685 68...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 203ms
memory: 3620kb

input:

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

output:

0 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 25...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 50...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 362 36...

result:

ok Accepted

Test #26:

score: 0
Accepted
time: 212ms
memory: 3656kb

input:

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

output:

0 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 6...

result:

ok Accepted

Test #27:

score: 0
Accepted
time: 203ms
memory: 3724kb

input:

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

output:

0 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 13...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 10...

result:

ok Accepted

Test #29:

score: 0
Accepted
time: 209ms
memory: 3624kb

input:

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

output:

0 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 290 29...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 312 31...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 417 41...

result:

ok Accepted

Test #32:

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

input:

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

output:

0 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 621 62...

result:

ok Accepted

Test #33:

score: 0
Accepted
time: 205ms
memory: 3720kb

input:

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

output:

0 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 967 96...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 558 55...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 11...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 519 51...

result:

ok Accepted

Test #37:

score: 0
Accepted
time: 198ms
memory: 3624kb

input:

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

output:

0 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 373 37...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 253 25...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 219ms
memory: 3656kb

input:

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

output:

0 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 713 71...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 848 84...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 ...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed