QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114822#6303. InversiontarjenAC ✓159ms3620kbC++171.5kb2023-06-23 17:23:442023-06-23 17:23:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-23 17:23:45]
  • 评测
  • 测评结果:AC
  • 用时:159ms
  • 内存:3620kb
  • [2023-06-23 17:23:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
int a[maxn],n;
struct tree{
    int c[maxn];
    int lowbit(int x){
        return x&-x;
    }
    void init(){
        memset(c,0,sizeof(c));
    }
    int getsum(int x){
        int sum=0;
        while(x>0){
            sum+=c[x];
            x-=lowbit(x);
        }
        return sum;
    }
    void update(int i,int x)
    {
        while(i<=n){
            c[x]+=x;
            i+=lowbit(i);
        }
    }
};
tree tri;
int query(int l,int r){
    cout<<"? "<<l<<" "<<r<<endl;cout.flush();
    int x;cin>>x;return x;
}
int id[maxn];
int G[maxn][maxn];
int get(int x,int l,int r)
{
    int z=0;
    // cout<<"??\n";
    for(int i=l;i<=r;i++)if(a[x]>a[i])z^=1;
    // cout<<"??\n";
    return z;
}
int main()
{
    cin>>n;
    a[1]=1;
    id[1]=1;
    for(int i=2;i<=n;i++){
        int l=1,r=i-1,res=i;
        while(l<=r){
            int mid=(l+r)/2;
            int x=query(id[mid],i);
            int y=query(id[mid]+1,i);
            // int z=get(id[mid],i-1);
            int z=get(id[mid],id[mid]+1,i-1);
            x^=y;
            x^=z;
            if(x==1){
                res=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        a[i]=res;
        // cout<<"res="<<res<<"\n";e
        for(int j=1;j<i;j++)if(a[j]>=res)a[j]++;
        for(int j=1;j<=i;j++)id[a[j]]=j;
    }
    cout<<"!";
    for(int i=1;i<=n;i++)cout<<" "<<a[i];
    cout<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3440kb

input:

3
0
0
0
1

output:

? 1 2
? 2 2
? 1 3
? 2 3
! 2 3 1

result:

ok OK, guesses=4

Test #2:

score: 0
Accepted
time: 136ms
memory: 3452kb

input:

1993
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
0
1
1
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
0
1
0
0
1
0
1
1
0
0
1
0
1
1
0
1
1
0
1
1
0
0
1
0
0...

output:

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

result:

ok OK, guesses=38180

Test #3:

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

input:

1887
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
1
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
0
1
1
0
1
1
0
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
1
0
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
1
0
1
1
0
0
1
0
1
0...

output:

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

result:

ok OK, guesses=35868

Test #4:

score: 0
Accepted
time: 126ms
memory: 3432kb

input:

1882
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
0
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
0
0
0
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
0
1
1
0
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
0
1
1
1
1
1
1
1
0
0
0
1
1
0
1
0
0
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
1
1...

output:

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

result:

ok OK, guesses=35724

Test #5:

score: 0
Accepted
time: 121ms
memory: 3560kb

input:

1877
0
0
0
1
1
0
0
0
1
1
0
1
0
1
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
1
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
0
0
1
1
0
0
0
0
0...

output:

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

result:

ok OK, guesses=35658

Test #6:

score: 0
Accepted
time: 159ms
memory: 3392kb

input:

1871
1
0
0
0
0
0
1
0
0
1
0
1
1
0
1
0
0
0
0
1
1
1
0
1
1
1
0
1
1
0
1
0
1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
0
1
1
0
1
1
1
0
1
0
0
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
1
1
0
1
1
0
0
1
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
0
0
1
0
1
0
0
1
0
1
1
0
1
0...

output:

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

result:

ok OK, guesses=35514

Test #7:

score: 0
Accepted
time: 91ms
memory: 3464kb

input:

1994
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

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

result:

ok OK, guesses=39774

Test #8:

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

input:

1990
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
1
0
1
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
1
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
1...

output:

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

result:

ok OK, guesses=38916

Test #9:

score: 0
Accepted
time: 85ms
memory: 3448kb

input:

1981
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
0
0
1
1
0
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
1
1
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1...

output:

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

result:

ok OK, guesses=38320

Test #10:

score: 0
Accepted
time: 59ms
memory: 3448kb

input:

1988
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
1
1
0
1
0
1
1
1
1
1
1
0
1
0
0
0
1
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
0
0
1
1
1
1
0
0
1
0
1
0
0
0
0...

output:

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

result:

ok OK, guesses=38314

Test #11:

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

input:

1991
0
0
1
1
1
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
1
0
0
1
1
0
1
0
0
1
0
1
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
1
1
0
1
1
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
1
1
0
0
0
1
1
0
0
1
1
1
0
0
1
1
0
1
0
1
0
0
1
1
1
0
0
0
1
1
0
1
1
0
1
0
0...

output:

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

result:

ok OK, guesses=38268

Test #12:

score: 0
Accepted
time: 105ms
memory: 3452kb

input:

1996
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
1
0
1
1
0
1
0
0
1
1
1
1
1
0
1
0
1
1
0
0
1
1
1
0
0
0
1
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
0
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
1
0
1
1
0
1
1
0
1
0
0
1
0
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0...

output:

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

result:

ok OK, guesses=38224

Test #13:

score: 0
Accepted
time: 90ms
memory: 3460kb

input:

1992
1
0
1
0
1
1
1
0
1
1
1
0
0
1
1
0
0
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
1
1
0
1
0
0
0
1
1
1
0
1
0
0
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0...

output:

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

result:

ok OK, guesses=35768

Test #14:

score: 0
Accepted
time: 79ms
memory: 3448kb

input:

1988
1
0
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
1
1
0
1
0
0
1
1
0
0
1
1
0
0
1
0
1
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
1
1
0
1
1
0
0
1
1
1
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
0
1
1
0
0
0
1
0
1
1
0
0
0
1
1
1
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
1
1
1
0
1
1
0
0
1
1
1
0
1
1
1
0
1
0
1
0
0
1
1
0
1
1
0
0
1
1
1
1
0
1
1
0
0
1...

output:

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

result:

ok OK, guesses=37068

Test #15:

score: 0
Accepted
time: 93ms
memory: 3448kb

input:

1983
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
1
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
1
0...

output:

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

result:

ok OK, guesses=37512

Test #16:

score: 0
Accepted
time: 103ms
memory: 3392kb

input:

1990
1
0
0
0
1
0
1
1
1
1
0
0
1
0
0
0
1
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
1
0
1
0
1
1
0
1
0
0
1
1
1
0
0
1
0
0
1
0
1
1
0
0
1
0
1
0
1
0
0
0
0
0
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
0
0
0
0
1
0
0
0
1
0
1
1
0
1
0
0
0
0
1
0
1
1
0
0
1
1
1
1
1
0
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1...

output:

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

result:

ok OK, guesses=37778

Test #17:

score: 0
Accepted
time: 84ms
memory: 3440kb

input:

1989
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
1
0
1
0
0
1
1
0
1
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
1
0
0
0
0
1
0
0
1
1
1
1
1
1
1
0
1
1
1
1
0
1
0
0
1
0
1
0
0
1
1
1
1
0
0
1
1
0
0
0
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
0
1
0
0
1
0
0
0
1
1
1
1
0
1
0
1
1
0
0
0
1
1
1
1
1
0
0...

output:

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

result:

ok OK, guesses=37956

Test #18:

score: 0
Accepted
time: 119ms
memory: 3392kb

input:

1998
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
1
0
1
0
1
1
1
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
0
0
0
0
0
0
0
1
1
1
1
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
1
0
1
1
0
0
1
1
0
0
0
1
0
0
1
0
1...

output:

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

result:

ok OK, guesses=38220

Test #19:

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

input:

1

output:

! 1

result:

ok OK, guesses=0

Test #20:

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

input:

2
0
0

output:

? 1 2
? 2 2
! 1 2

result:

ok OK, guesses=2

Test #21:

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

input:

2
1
0

output:

? 1 2
? 2 2
! 2 1

result:

ok OK, guesses=2

Test #22:

score: 0
Accepted
time: 125ms
memory: 3528kb

input:

1997
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1...

output:

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

result:

ok OK, guesses=38818

Test #23:

score: 0
Accepted
time: 66ms
memory: 3448kb

input:

1998
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1...

output:

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

result:

ok OK, guesses=38840

Test #24:

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

input:

1999
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1...

output:

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

result:

ok OK, guesses=38862

Test #25:

score: 0
Accepted
time: 59ms
memory: 3564kb

input:

2000
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1...

output:

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

result:

ok OK, guesses=38884