QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731706#9432. PermutationTheZoneAC ✓222ms3960kbC++202.9kb2024-11-10 10:37:252024-11-10 10:37:28

Judging History

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

  • [2024-11-10 10:37:28]
  • 评测
  • 测评结果:AC
  • 用时:222ms
  • 内存:3960kb
  • [2024-11-10 10:37:25]
  • 提交

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(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n;
    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];
    cout << endl;}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 196ms
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: 3632kb

input:

1

output:

1 1

result:

ok Accepted

Test #4:

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

input:

2
2

output:

0 2 1
1 2 1

result:

ok Accepted

Test #5:

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

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: 3636kb

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: 3840kb

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: 0ms
memory: 3864kb

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: 3800kb

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: 0ms
memory: 3576kb

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: 3636kb

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: 1ms
memory: 3652kb

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: 3832kb

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: 0ms
memory: 3636kb

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: 3648kb

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: 1ms
memory: 3568kb

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: 180ms
memory: 3716kb

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: 3696kb

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: 188ms
memory: 3724kb

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: 190ms
memory: 3728kb

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: 189ms
memory: 3692kb

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: 205ms
memory: 3920kb

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: 202ms
memory: 3916kb

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: 193ms
memory: 3664kb

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: 201ms
memory: 3720kb

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: 222ms
memory: 3960kb

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: 196ms
memory: 3764kb

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: 187ms
memory: 3660kb

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: 198ms
memory: 3720kb

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: 185ms
memory: 3720kb

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: 201ms
memory: 3888kb

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: 192ms
memory: 3956kb

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: 210ms
memory: 3652kb

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: 210ms
memory: 3660kb

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: 191ms
memory: 3724kb

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: 188ms
memory: 3724kb

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: 3924kb

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: 193ms
memory: 3668kb

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: 3716kb

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: 210ms
memory: 3724kb

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: 202ms
memory: 3720kb

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