QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740758#9432. Permutation-xcxxx-AC ✓295ms4088kbC++142.8kb2024-11-13 11:21:572024-11-13 11:21:57

Judging History

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

  • [2024-11-13 11:21:57]
  • 评测
  • 测评结果:AC
  • 用时:295ms
  • 内存:4088kb
  • [2024-11-13 11:21:57]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
using namespace std;
int rd() {int x=0,f=1;char c=getchar();while(!isdigit(c))f=(c=='-'?-1:f),c=getchar();while(isdigit(c))x=x*10+c-'0',c=getchar();return x*f;}
const int N=1005;
int n,p[N],ans[N];
int out[N];
#ifdef ONLINE_JUDGE
void init() {
}
int query(vector<int> ask) {
    assert(ask.size()==n);
    rep(i,0,n-1) out[p[i+1]]=ask[i];
    printf("0 ");rep(i,1,n)printf("%d ",out[i]);
    puts(""),fflush(stdout);
    int res;cin>>res;
    return res;
}
#endif
#ifndef ONLINE_JUDGE
int a[N],qcnt;
void init() {
    rep(i,1,n) a[i]=i;
    random_shuffle(a+1,a+1+n);
    printf("ANS: ");rep(i,1,n) printf("%d ",a[i]);puts("");
}
int query(vector<int> ask) {
    qcnt++;
    rep(i,0,n-1) out[p[i+1]]=ask[i];
    printf("0 ");rep(i,1,n)printf("%d ",out[i]);
    puts(""),fflush(stdout);
    int cnt=0;
    rep(i,1,n) cnt+=out[i]==a[i];
    printf("%d\n",cnt);
    return cnt;
}
#endif
void solve(int l,int r,vector<int> now) {
    // fprintf(stderr,"l=%d r=%d\n",l,r);
    if(l==r) {
        ans[p[l]]=now[0];
        return;
    }
    int mid=(l+r)>>1;
    vector<int> L,R,unknown;
    unknown.push_back(now.back());
    now.pop_back();
    for(int x:now) {
        if(L.size()==mid-l+1) {R.push_back(x);continue;}
        if(R.size()==r-mid) {L.push_back(x);continue;}
        if(unknown.empty()) {unknown.push_back(x);continue;}
        vector<int> ask;
        rep(i,1,l-1) ask.push_back(x);
        rep(i,l,mid) ask.push_back(x);
        rep(i,mid+1,r) ask.push_back(unknown.front());
        rep(i,r+1,n) ask.push_back(x);
        int val=query(ask);
        if(val==0) {
            R.push_back(x);
            for(int y:unknown) L.push_back(y);
            unknown.clear();
        }
        if(val==2) {
            L.push_back(x);
            for(int y:unknown) R.push_back(y);
            unknown.clear();
        }
        if(val==1) unknown.push_back(x);
        // printf("L: ");for(int x:L) printf("%d ",x);puts("");
        // printf("R: ");for(int x:R) printf("%d ",x);puts("");
        // printf("unknown: ");for(int x:unknown) printf("%d ",x);puts("");
    }
    if(L.size()<mid-l+1) for(int x:unknown) L.push_back(x);
    if(R.size()<r-mid) for(int x:unknown) R.push_back(x);
    solve(l, mid ,L);
    solve(mid+1,r,R);
}
signed main() {
    srand(random_device{}());
    // freopen("K.out","w",stdout);
    n=rd();
    init();
    rep(i,1,n) p[i]=i;
    random_shuffle(p+1,p+1+n);
    vector<int> now;
    rep(i,1,n) now.push_back(i);
    solve(1,n,now);
    printf("1 ");
    rep(i,1,n) printf("%d ",ans[i]);
    puts("");
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%d queries\n",qcnt);
    #endif
    return 0;
}
//g++ -fsanitize=address,undefined -Wall -std=c++14 -O2 -o K K.cpp

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1
2
2
0
2

output:

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

result:

ok Accepted

Test #2:

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

input:

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

output:

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

result:

ok Accepted

Test #3:

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

input:

1

output:

1 1 

result:

ok Accepted

Test #4:

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

input:

2
0

output:

0 1 2 
1 2 1 

result:

ok Accepted

Test #5:

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

input:

3
1
0
2

output:

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

result:

ok Accepted

Test #6:

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

input:

4
1
2
2
0

output:

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

result:

ok Accepted

Test #7:

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

input:

6
1
2
0
0
0
0
0

output:

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

result:

ok Accepted

Test #8:

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

input:

7
0
2
0
1
0
0
0
1
0
2

output:

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

result:

ok Accepted

Test #9:

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

input:

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

output:

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

result:

ok Accepted

Test #10:

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

input:

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

output:

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

result:

ok Accepted

Test #11:

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

input:

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

output:

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

result:

ok Accepted

Test #12:

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

input:

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

output:

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

result:

ok Accepted

Test #13:

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

input:

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

output:

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

result:

ok Accepted

Test #14:

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

input:

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

output:

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

result:

ok Accepted

Test #15:

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

input:

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

output:

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

result:

ok Accepted

Test #16:

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

input:

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

output:

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

result:

ok Accepted

Test #17:

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

input:

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

output:

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

result:

ok Accepted

Test #18:

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

input:

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

output:

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

result:

ok Accepted

Test #19:

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

input:

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

output:

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

result:

ok Accepted

Test #20:

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

input:

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

output:

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

result:

ok Accepted

Test #21:

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

input:

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

output:

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

result:

ok Accepted

Test #22:

score: 0
Accepted
time: 289ms
memory: 4040kb

input:

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

output:

0 1 1 1 980 1 980 980 1 980 1 980 1 1 1 980 980 1 1 980 1 980 980 1 980 980 1 980 1 980 1 1 980 1 980 1 1 980 1 980 980 1 1 1 980 980 980 980 980 1 980 980 980 1 980 980 1 980 1 980 980 980 980 980 980 980 1 980 1 1 980 980 1 980 980 980 980 980 1 1 980 980 980 1 1 1 1 1 980 1 1 980 980 980 1 980 98...

result:

ok Accepted

Test #23:

score: 0
Accepted
time: 262ms
memory: 3844kb

input:

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

output:

0 981 981 1 981 1 1 981 1 981 1 981 981 1 981 1 1 1 981 981 1 981 981 981 1 1 981 981 981 1 1 981 981 1 981 1 981 981 981 1 981 981 981 981 981 1 1 981 1 981 1 981 981 981 1 1 1 981 1 981 1 981 981 981 1 1 1 981 1 981 1 981 1 1 1 1 1 981 1 981 1 981 1 981 981 981 1 981 981 1 981 981 1 981 981 981 98...

result:

ok Accepted

Test #24:

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

input:

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

output:

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

result:

ok Accepted

Test #25:

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

input:

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

output:

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

result:

ok Accepted

Test #26:

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

input:

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

output:

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

result:

ok Accepted

Test #27:

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

input:

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

output:

0 985 985 985 1 985 1 1 1 985 985 1 1 985 985 1 1 985 985 1 985 985 985 985 985 985 985 985 985 1 985 985 985 985 985 1 1 985 1 1 1 985 985 985 1 985 1 985 985 1 985 985 985 1 985 1 1 985 1 985 1 985 1 985 1 1 1 985 985 1 985 1 1 1 1 985 985 1 985 985 1 1 985 985 1 985 985 985 985 1 985 985 1 1 1 98...

result:

ok Accepted

Test #28:

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

input:

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

output:

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

result:

ok Accepted

Test #29:

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

input:

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

output:

0 1 987 1 1 987 1 1 987 987 987 987 1 987 987 987 987 1 1 1 1 987 987 1 987 987 987 987 987 1 987 987 1 987 1 1 1 987 987 987 987 987 987 1 1 987 987 987 987 987 987 1 987 1 1 1 987 987 1 987 987 1 1 1 987 1 1 1 1 987 987 1 987 1 987 1 1 1 1 1 1 1 1 1 987 1 1 1 987 1 1 987 1 987 1 987 987 987 1 1 98...

result:

ok Accepted

Test #30:

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

input:

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

output:

0 988 1 988 1 988 988 988 988 1 988 988 988 988 988 1 1 988 1 1 1 988 988 988 1 988 1 1 1 988 988 988 1 1 1 988 988 988 988 988 988 988 1 1 1 1 1 988 988 1 988 1 1 1 988 1 988 988 1 988 1 1 988 988 988 1 988 988 1 988 1 988 988 1 1 988 988 1 988 988 1 1 1 988 1 988 1 988 988 988 988 1 988 1 988 1 98...

result:

ok Accepted

Test #31:

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

input:

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

output:

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

result:

ok Accepted

Test #32:

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

input:

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

output:

0 990 1 990 1 990 990 990 1 1 1 990 1 990 1 990 990 990 1 990 990 990 990 990 990 990 990 1 990 1 1 990 990 1 1 1 1 1 1 1 990 990 1 990 990 1 990 1 1 1 1 1 1 990 1 1 1 990 1 1 990 1 990 1 1 990 990 1 990 990 990 1 990 990 990 1 990 990 990 1 990 990 1 990 990 990 1 990 1 1 1 1 990 1 1 990 990 990 99...

result:

ok Accepted

Test #33:

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

input:

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

output:

0 991 1 1 991 1 1 1 1 1 991 991 1 1 991 991 991 1 991 991 991 991 991 991 991 1 991 1 991 1 991 991 1 991 991 1 991 1 991 1 1 991 1 991 1 991 991 1 1 1 1 1 1 991 991 991 991 991 991 1 1 991 1 991 1 1 991 1 991 991 1 991 991 1 1 1 1 1 991 991 1 991 991 1 991 991 991 991 1 991 1 1 1 991 991 991 1 1 99...

result:

ok Accepted

Test #34:

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

input:

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

output:

0 1 1 1 992 1 992 1 1 992 992 1 1 1 1 1 992 992 1 992 1 992 1 992 992 1 992 992 992 992 1 992 992 1 1 992 992 992 992 992 1 992 1 1 1 1 992 992 992 992 1 1 1 1 992 1 992 1 992 992 992 1 1 992 1 1 992 992 992 992 1 1 992 992 992 992 992 992 992 1 1 1 1 992 1 992 992 992 992 1 1 1 992 1 1 1 1 992 1 99...

result:

ok Accepted

Test #35:

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

input:

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

output:

0 993 993 993 993 993 1 1 1 1 993 1 1 993 993 1 1 1 1 993 993 993 1 993 1 1 1 1 1 1 993 1 993 1 1 1 1 993 993 993 1 993 1 993 1 993 993 993 993 1 993 993 1 1 1 1 993 1 993 993 993 993 1 1 1 1 1 1 993 993 1 993 993 993 1 993 993 1 993 1 993 993 993 1 993 1 1 1 1 1 1 1 1 993 1 993 993 993 1 1 1 1 1 99...

result:

ok Accepted

Test #36:

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

input:

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

output:

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

result:

ok Accepted

Test #37:

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

input:

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

output:

0 995 995 995 995 995 995 995 995 995 1 995 1 1 995 1 1 995 995 995 1 1 1 1 995 995 995 995 1 995 1 1 1 1 1 995 995 1 1 995 995 1 995 995 1 995 995 995 995 1 1 995 1 995 995 995 1 1 995 995 995 1 1 995 1 995 995 995 1 995 995 995 1 995 995 995 1 995 1 1 995 1 1 995 995 995 1 995 1 1 995 995 1 995 99...

result:

ok Accepted

Test #38:

score: 0
Accepted
time: 267ms
memory: 4052kb

input:

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

output:

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

result:

ok Accepted

Test #39:

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

input:

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

output:

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

result:

ok Accepted

Test #40:

score: 0
Accepted
time: 275ms
memory: 3760kb

input:

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

output:

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

result:

ok Accepted

Test #41:

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

input:

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

output:

0 999 999 999 1 999 999 999 999 999 1 999 999 999 1 999 999 1 999 999 999 999 1 999 1 999 999 1 999 999 999 1 999 1 1 999 1 999 999 1 999 999 1 1 999 999 999 1 999 1 1 999 1 999 1 1 1 1 999 1 1 999 1 999 999 999 999 999 1 999 999 1 1 1 999 999 999 999 1 999 999 1 999 999 999 999 1 999 999 1 1 1 1 99...

result:

ok Accepted

Extra Test:

score: 0
Extra Test Passed