QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743425#9432. PermutationKellyWLJAC ✓332ms3852kbC++173.1kb2024-11-13 19:12:032024-11-13 19:12:04

Judging History

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

  • [2024-11-13 19:12:04]
  • 评测
  • 测评结果:AC
  • 用时:332ms
  • 内存:3852kb
  • [2024-11-13 19:12:03]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

const int N = 1010; using pii = pair<int, int>;
mt19937 rnd(std::chrono::steady_clock().now().time_since_epoch().count());
int n, vis[N], b[N], a[N], p[N];
int T;
struct DSU {
    int fa[N];
    void init() {for(int i = 1; i <= n; ++i)    fa[i] = i;}
    int find(int x) {return x != fa[x] ? fa[x] = find(fa[x]) : x;}
    void merge(int x, int y)    {x = find(x), y = find(y);  fa[x] = y;}
}dsu;
int ask(int x, int y, int els, int l, int mid, int r) {
    memset(p, 0, sizeof(p)), ++T;
    // if(T > 6666) {
    //     cout << "1 ";
    //     for(int i = 1; i <= n; ++i) cout << i << " ";
    //     cout << "\n";   exit(0);
    // }
    for(int i = l; i <= mid; ++i)   p[i] = x;
    for(int i = mid + 1; i <= r; ++i)   p[i] = y;
    for(int i = 1; i <= n; ++i) if(!p[i])   p[i] = els;
    cout << "0 ";
    for(int i = 1; i <= n; ++i) cout << p[i] << " ";
    cout << endl;   int res = 0;
    #ifdef Kelly 
        for(int i = 1; i <= n; ++i) res += p[i] == b[i];
        return res;
    #endif 
    cin >> res; return res;
}
void solve(int l, int r, vector<int> p) {
    if(l > r || p.empty())  return;
    if(l == r)  return void(a[l] = p[0]);
    int mid = (l + r) >> 1;
    vector<int> tmpl, tmpr, tmp = p; vector<pii> lsh;
    int nw = p[0];
    dsu.init();
    auto del = [&](int x) -> void   {swap(p[x], p.back()), p.pop_back();};
    // cerr << l << " " << r << " " << mid << "\n";
    // for(int x : p)  cerr << x << " ";
    // cerr << "\n";
    while(p.size() > 1) {
        int x = rnd() % p.size(), y = rnd() % p.size();
        while(y == x)   y = rnd() % p.size();
        if(x > y)   swap(x, y);
        int u = p[x], v = p[y];
        del(y), del(x);
        int sum = ask(u, v, nw, l, mid, r);
        if(sum == 0)    tmpl.pb(v), tmpr.pb(u);
        else if(sum == 2)   tmpl.pb(u), tmpr.pb(v);
        else    dsu.merge(u, v), p.pb(dsu.find(v));
    }
    if(p.size()) {
        int res = ask(tmpr[0], p[0], tmpr[0], l, mid, r);
        if(res) tmpr.pb(p[0]);
        else    tmpl.pb(p[0]);
    }
    memset(vis, 0, sizeof(vis));
    for(int x : tmpl)   vis[x] = 1;
    for(int x : tmpr)   vis[x] = 2;
    for(int x : tmp)    if(!vis[x]) vis[dsu.find(x)] == 1 ? tmpl.pb(x) : tmpr.pb(x);
    solve(l, mid, tmpl), solve(mid + 1, r, tmpr);
}
int main() {
    #ifdef Kelly
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    cin >> n;
    #ifdef Kelly
        for(int i = 1; i <= n; ++i) n <= 10 ? void(cin >> b[i]) : void(b[i] = i);
        if(n > 10) {
            shuffle(b + 1, b + n + 1, rnd);
            for(int i = 1; i <= n; ++i) cerr << b[i] << " ";
            cerr << "\n";
        }
    #endif
    vector<int> tmp;
    for(int i = 1; i <= n; ++i) tmp.pb(i);
    solve(1, n, tmp);
    cout << "1 ";
    for(int i = 1; i <= n; ++i) cout << a[i] << " ";
    cout << endl;
    #ifdef Kelly
        cerr << T << "\n";
        for(int i = 1; i <= n; ++i) if(a[i] != b[i])    cerr << i << "\n";
    #endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
2
0
0
0
0
0
0

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

0 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 661 66...

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
0

output:

0 1 2 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
2
0
0

output:

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

result:

ok Accepted

Test #6:

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

input:

4
1
2
0
2
2

output:

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

result:

ok Accepted

Test #7:

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

input:

6
2
0
0
2
0
0
2
0
2

output:

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

result:

ok Accepted

Test #8:

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

input:

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

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

0 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 26...

result:

ok Accepted

Test #18:

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

input:

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

output:

0 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 49...

result:

ok Accepted

Test #19:

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

input:

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

output:

0 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 9...

result:

ok Accepted

Test #20:

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

input:

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

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

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

input:

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

output:

0 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 6...

result:

ok Accepted

Test #22:

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

input:

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

output:

0 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

result:

ok Accepted

Test #23:

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

input:

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

output:

0 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 336 33...

result:

ok Accepted

Test #24:

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

input:

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

output:

0 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 358 35...

result:

ok Accepted

Test #25:

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

input:

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

output:

0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

result:

ok Accepted

Test #26:

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

input:

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

output:

0 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...

result:

ok Accepted

Test #27:

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

input:

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

output:

0 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 7...

result:

ok Accepted

Test #28:

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

input:

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

output:

0 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 130 13...

result:

ok Accepted

Test #29:

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

input:

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

output:

0 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 599 59...

result:

ok Accepted

Test #30:

score: 0
Accepted
time: 293ms
memory: 3692kb

input:

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

output:

0 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 118 11...

result:

ok Accepted

Test #31:

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

input:

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

output:

0 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 40...

result:

ok Accepted

Test #32:

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

input:

990
2
1
0
2
2
1
0
1
0
2
0
2
0
1
1
2
2
1
0
1
0
1
1
1
2
2
2
2
0
1
1
1
1
1
2
2
2
2
0
1
0
0
2
1
0
0
0
1
1
1
1
2
2
0
2
1
0
1
1
1
1
2
0
1
0
1
1
2
1
1
1
0
1
1
1
2
2
2
1
1
1
2
0
2
0
0
0
1
0
0
2
2
1
1
1
1
0
1
1
1
0
2
2
2
0
0
0
1
2
1
0
2
1
1
0
1
0
2
2
1
1
1
1
2
2
1
2
2
2
2
1
1
2
1
1
1
2
1
0
1
0
1
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 #33:

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

input:

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

output:

0 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 6...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 6...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 648 64...

result:

ok Accepted

Test #36:

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

input:

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

output:

0 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 627 62...

result:

ok Accepted

Test #37:

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

input:

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

output:

0 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 465 46...

result:

ok Accepted

Test #38:

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

input:

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

output:

0 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 529 52...

result:

ok Accepted

Test #39:

score: 0
Accepted
time: 283ms
memory: 3712kb

input:

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

output:

0 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 29...

result:

ok Accepted

Test #40:

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

input:

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

output:

0 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 110 11...

result:

ok Accepted

Test #41:

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

input:

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

output:

0 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 223 22...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed