QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#610600#9432. Permutationpropane#AC ✓216ms3940kbC++203.3kb2024-10-04 16:34:332024-10-04 16:34:35

Judging History

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

  • [2024-10-04 16:34:35]
  • 评测
  • 测评结果:AC
  • 用时:216ms
  • 内存:3940kb
  • [2024-10-04 16:34:33]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<random>
#include<numeric>
#include<cassert>
#include<algorithm>
using namespace std;
using LL = long long;
mt19937_64 rnd(1243214124);
int n;
int a[1005], p[1005], target[1005];

int cnt;

int ask(){
    cnt += 1;
    cout << "0";
    for(int i = 1; i <= n; i++){
        cout << ' ' << a[i];
    }
    cout << endl;

// #ifdef LOCAL
//     int ans = 0;
//     for(int i = 1; i <= n; i++) ans += (a[i] == target[i]);
//     return ans;
// #endif

    int t;
    cin >> t;
    return t;
}

int type[1005];

namespace DSU{
    int p[1005];
    vector<int> s[1005];

    void init(const vector<int> &v){
        for(auto x : v){
            p[x] = x;
            s[x] = {x};
        }
    }

    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        if (x != y){
            if (s[x].size() > s[y].size()){
                swap(x, y);
            }
            p[x] = y;
            for(auto u : s[x]) s[y].push_back(u);
        }
    }

}

void solve(int l, int r, vector<int> v){
    if (l == r){
        p[r] = v[0];
        return;
    }
    shuffle(v.begin(), v.end(), rnd);
    int mid = (l + r) / 2;
    vector<int> vl, vr;
    DSU::init(v);
    while(!v.empty()){
        if (v.size() == 1){
            if (vl.size() < mid - l + 1){
                for(auto u : DSU::s[DSU::find(v.back())]){
                    vl.push_back(u);
                }
            }
            else{
                for(auto u : DSU::s[DSU::find(v.back())]){
                    vr.push_back(u);
                }
            }
            break;
        }
        int t1 = v.back();
        v.pop_back();
        int t2 = v.back();
        v.pop_back();
        for(int i = 1; i <= mid; i++){
            a[i] = t1;
        }
        for(int i = mid + 1; i <= n; i++){
            a[i] = t2;
        }
        int cnt = ask();
        if (cnt == 1){
            DSU::merge(t1, t2);
            v.push_back(DSU::find(t1));
        }
        else if (cnt == 2){
            for(auto u : DSU::s[DSU::find(t1)]){
                vl.push_back(u);
            }
            for(auto u : DSU::s[DSU::find(t2)]){
                vr.push_back(u);
            }
        }
        else{
            for(auto u : DSU::s[DSU::find(t1)]){
                vr.push_back(u);
            }
            for(auto u : DSU::s[DSU::find(t2)]){
                vl.push_back(u);
            }
        }
    }
    solve(l, mid, vl);
    solve(mid + 1, r, vr);
}

int main(){

// #ifdef LOCAL
//     freopen("data.in", "r", stdin);
//     freopen("data.out", "w", stdout);
// #endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;
    // vector<int> v{4, 3, 2, 1, 5};
    // vector<int> v(n);
    // iota(v.begin(), v.end(), 1);
    // shuffle(v.begin(), v.end(), rnd);
    // for(int i = 1; i <= n; i++) target[i] = v[i - 1];

    vector<int> q(n);
    iota(q.begin(), q.end(), 1);
    solve(1, n, q);
    cout << "1";
    for(int i = 1; i <= n; i++) cout << ' ' << p[i];
    // for(int i = 1; i <= n; i++) assert(p[i] == target[i]);
    cout << endl;
    // assert(cnt <= 6666);
    // cout << cnt << '\n';

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1
2
2
0
0
2

output:

0 4 4 4 2 2
0 2 2 2 5 5
0 3 3 3 1 1
0 2 2 4 4 4
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: 214ms
memory: 3716kb

input:

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

output:

0 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 681 68...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1
1 2 1

result:

ok Accepted

Test #5:

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

input:

3
0
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
2
2
2
2

output:

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

result:

ok Accepted

Test #7:

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

input:

6
0
2
2
2
2
0
0

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

0 6 6 6 6 1 1 1 1
0 8 8 8 8 2 2 2 2
0 4 4 4 4 5 5 5 5
0 5 5 5 5 3 3 3 3
0 1 1 3 3 3 3 3 3
0 2 2 7 7 7 7 7 7
0 7 3 3 3 3 3 3 3
0 1 1 1 2 2 2 2 2
0 5 5 5 5 5 5 4 4
0 6 6 6 6 6 6 8 8
0 6 6 6 6 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: 3616kb

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

0 2 2 2 2 2 2 2 2 12 12 12 12 12 12 12
0 12 12 12 12 12 12 12 12 3 3 3 3 3 3 3
0 12 12 12 12 12 12 12 12 11 11 11 11 11 11 11
0 5 5 5 5 5 5 5 5 9 9 9 9 9 9 9
0 14 14 14 14 14 14 14 14 1 1 1 1 1 1 1
0 10 10 10 10 10 10 10 10 15 15 15 15 15 15 15
0 15 15 15 15 15 15 15 15 4 4 4 4 4 4 4
0 15 15 15 15 1...

result:

ok Accepted

Test #17:

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

input:

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

output:

0 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 10...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 439 43...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 45...

result:

ok Accepted

Test #20:

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

input:

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

output:

0 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 74...

result:

ok Accepted

Test #21:

score: 0
Accepted
time: 186ms
memory: 3596kb

input:

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

output:

0 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 8...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 897 89...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 17...

result:

ok Accepted

Test #24:

score: 0
Accepted
time: 201ms
memory: 3716kb

input:

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

output:

0 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 740 74...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 6...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 38...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 259 25...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 1...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 483 48...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 182ms
memory: 3728kb

input:

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

output:

0 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 870 87...

result:

ok Accepted

Test #31:

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

input:

989
0
2
1
0
0
1
1
2
1
2
2
0
0
2
1
0
2
2
2
1
1
0
1
2
1
1
1
0
2
0
2
0
0
0
0
1
1
1
2
1
2
1
0
1
2
1
0
2
2
2
0
0
1
1
2
1
0
2
0
1
1
1
0
2
0
1
2
2
2
0
1
1
0
1
1
1
1
1
0
0
1
1
1
0
2
1
1
2
1
0
1
0
1
1
1
1
1
1
1
1
2
1
1
0
2
1
2
2
1
1
1
2
1
1
1
0
1
2
1
1
1
2
2
1
0
1
0
1
1
1
2
2
2
1
2
2
1
0
1
1
1
0
1
0
2
0
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 #32:

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

input:

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

output:

0 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 453 45...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 686 68...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 827 82...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 571 57...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 602 60...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 458 45...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 878 87...

result:

ok Accepted

Test #39:

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

input:

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

output:

0 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 585 58...

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 197ms
memory: 3888kb

input:

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

output:

0 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 261 26...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 676 67...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed