QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#465511#6303. InversionBalintRAC ✓79ms3908kbC++202.1kb2024-07-06 23:39:442024-07-06 23:39:44

Judging History

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

  • [2024-07-06 23:39:44]
  • 评测
  • 测评结果:AC
  • 用时:79ms
  • 内存:3908kb
  • [2024-07-06 23:39:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

const int MN = 2005;
int n;

int query(int l, int r){
    if(r-l <= 1) return 0;
    cout << "? " << l+1 << ' ' << r << endl;
    int res; cin >> res;
    return res;
}

vi ord;
int suf[MN], tmp[MN];

bool cmp(int l, int r){
    int v1 = (query(l+1, r+1) ^ suf[l+1]) & 1;
    int v2 = (query(l, r+1) ^ suf[l]) & 1;
    return v1 ^ v2;
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FR(p, n){
        int lo = 0, hi = SZ(ord);
        while(lo < hi){
            int mid = (lo+hi)/2;
            if(cmp(ord[mid], p)) hi = mid;
            else lo = mid+1;
        }
        ord.insert(ord.begin()+lo, p);

        FOR(i, lo+1, SZ(ord)) tmp[ord[i]]++;
        FORR(i, p-1, 0) suf[i] += tmp[i] += tmp[i+1];
        ms(tmp, 0);
    }

    vi mp(n);
    FR(i, n) mp[ord[i]] = i;
    cout << "!";
    FR(i, n) cout << ' ' << mp[i]+1;
    cout << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0
1
1
0

output:

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

result:

ok OK, guesses=4

Test #2:

score: 0
Accepted
time: 25ms
memory: 3600kb

input:

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

output:

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

result:

ok OK, guesses=38238

Test #3:

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

input:

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

output:

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

result:

ok OK, guesses=35786

Test #4:

score: 0
Accepted
time: 55ms
memory: 3600kb

input:

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

output:

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

result:

ok OK, guesses=35742

Test #5:

score: 0
Accepted
time: 56ms
memory: 3904kb

input:

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

output:

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

result:

ok OK, guesses=35536

Test #6:

score: 0
Accepted
time: 58ms
memory: 3868kb

input:

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

output:

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

result:

ok OK, guesses=35460

Test #7:

score: 0
Accepted
time: 33ms
memory: 3876kb

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 3
? 3 4
? 2 4
? 3 4
? 4 5
? 3 5
? 4 5
? 4 6
? 3 6
? 5 6
? 5 7
? 4 7
? 6 7
? 5 8
? 4 8
? 7 8
? 6 8
? 7 8
? 6 9
? 5 9
? 8 9
? 7 9
? 8 9
? 6 10
? 5 10
? 9 10
? 8 10
? 9 10
? 7 11
? 6 11
? 10 11
? 9 11
? 10 11
? 7 12
? 6 12
? 10 12
? 9 12
? 11 12
? 8 13
? 7 13
? 11 13
? 10 13
? 12 13
? 8 14
? ...

result:

ok OK, guesses=33815

Test #8:

score: 0
Accepted
time: 47ms
memory: 3896kb

input:

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

output:

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

result:

ok OK, guesses=36474

Test #9:

score: 0
Accepted
time: 50ms
memory: 3608kb

input:

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

output:

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

result:

ok OK, guesses=37120

Test #10:

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

input:

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

output:

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

result:

ok OK, guesses=37548

Test #11:

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

input:

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

output:

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

result:

ok OK, guesses=37935

Test #12:

score: 0
Accepted
time: 33ms
memory: 3600kb

input:

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

output:

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

result:

ok OK, guesses=38191

Test #13:

score: 0
Accepted
time: 43ms
memory: 3896kb

input:

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

output:

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

result:

ok OK, guesses=37739

Test #14:

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

input:

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

output:

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

result:

ok OK, guesses=38142

Test #15:

score: 0
Accepted
time: 43ms
memory: 3608kb

input:

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

output:

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

result:

ok OK, guesses=38067

Test #16:

score: 0
Accepted
time: 39ms
memory: 3908kb

input:

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

output:

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

result:

ok OK, guesses=38276

Test #17:

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

input:

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

output:

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

result:

ok OK, guesses=38092

Test #18:

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

input:

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

output:

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

result:

ok OK, guesses=38262

Test #19:

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

input:

1

output:

! 1

result:

ok OK, guesses=0

Test #20:

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

input:

2
0

output:

? 1 2
! 1 2

result:

ok OK, guesses=1

Test #21:

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

input:

2
1

output:

? 1 2
! 2 1

result:

ok OK, guesses=1

Test #22:

score: 0
Accepted
time: 43ms
memory: 3600kb

input:

1997
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
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
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
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1...

output:

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

result:

ok OK, guesses=35867

Test #23:

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

input:

1998
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
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
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
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1...

output:

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

result:

ok OK, guesses=35888

Test #24:

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

input:

1999
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
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
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
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1...

output:

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

result:

ok OK, guesses=35907

Test #25:

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

input:

2000
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
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
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
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1...

output:

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

result:

ok OK, guesses=35928