QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95334#6303. InversionAndycipationAC ✓305ms5900kbC++172.3kb2023-04-09 14:39:532023-04-14 01:26:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-14 01:26:16]
  • 评测
  • 测评结果:AC
  • 用时:305ms
  • 内存:5900kb
  • [2023-04-09 14:39:53]
  • 提交

answer

/*
 * author:  ADMathNoob
 * created: 04/09/23 02:38:36
 * problem: https://qoj.ac/problem/6303
 */

/*
Comments about problem:


*/

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
#include "../.cp/algorithms/debug/debug.h"
#else
#define debug(...) 42
#endif

#ifdef _DEBUG

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int RandInt(int low, int high) {
  return low + (rng() % (high - low + 1));
}

int used = 0;
vector<int> answer;

int Ask(int L, int R) {
  assert(++used <= 40000);
  int ret = 0;
  for (int i = L; i <= R; i++) {
    for (int j = i + 1; j <= R; j++) {
      if (answer[i] > answer[j]) {
        ret += 1;
      }
    }
  }
  return ret % 2;
}

void Answer(const vector<int>& p) {
  debug(p, answer);
  assert(p == answer);
}

#else

int used = 0;
map<pair<int, int>, int> mp;

int Ask(int L, int R) {
  if (L == R) return 0;
  if (!mp.count({L, R})) {
    assert(++used <= 40000);
    cout << "? " << L + 1 << ' ' << R + 1 << endl;
    cin >> mp[{L, R}];
  }
  return mp[{L, R}];
}

void Answer(const vector<int>& p) {
  cout << "!";
  for (int x : p) {
    cout << ' ' << x + 1;
  }
  cout << endl;
}

#endif

void SolveOne(int n) {
  vector<int> suf(1, 0);
  for (int it = 1; it < n; it++) {
    vector<int> pos(it);
    for (int i = 0; i < it; i++) {
      pos[suf[i]] = i;
    }
    const int at = n - it - 1;
    // look for smallest that is > x
    int low = 0, high = it;
    while (low < high) {
      int mid = (low + high) / 2;
      int cntL = 0;
      for (int i = 0; i < pos[mid]; i++) {
        cntL += (suf[i] > mid);
      }
      if ((Ask(at, at + pos[mid]) + cntL) % 2 == Ask(at, at + 1 + pos[mid])) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    for (int i = 0; i < it; i++) {
      if (suf[i] >= low) {
        suf[i] += 1;
      }
    }
    suf.insert(suf.begin(), low);
  }
  Answer(suf);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

#ifdef _DEBUG
  const int n = 100;
  for (int it = 0; it < 100; it++) {
    answer.resize(n);
    iota(answer.begin(), answer.end(), 0);
    shuffle(answer.begin(), answer.end(), rng);
    used = 0;
    SolveOne(n);
  }
  return 0;
#else
  int n;
  cin >> n;
  SolveOne(n);
  return 0;
#endif
}

详细

Test #1:

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

input:

3
1
0
0

output:

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

result:

ok OK, guesses=3

Test #2:

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

input:

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

output:

? 1992 1993
? 1991 1992
? 1991 1993
? 1990 1991
? 1990 1992
? 1990 1993
? 1989 1990
? 1989 1992
? 1989 1993
? 1988 1989
? 1988 1990
? 1988 1992
? 1988 1993
? 1987 1988
? 1987 1989
? 1987 1992
? 1987 1993
? 1986 1988
? 1986 1989
? 1986 1987
? 1985 1986
? 1985 1987
? 1985 1988
? 1985 1992
? 1985 1993
...

result:

ok OK, guesses=37877

Test #3:

score: 0
Accepted
time: 286ms
memory: 5716kb

input:

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

output:

? 1886 1887
? 1885 1886
? 1885 1887
? 1884 1885
? 1884 1886
? 1884 1887
? 1883 1884
? 1883 1886
? 1883 1887
? 1882 1883
? 1882 1884
? 1882 1886
? 1882 1887
? 1881 1882
? 1881 1886
? 1881 1887
? 1881 1883
? 1880 1881
? 1880 1882
? 1880 1883
? 1880 1886
? 1880 1887
? 1879 1880
? 1879 1881
? 1879 1883
...

result:

ok OK, guesses=35588

Test #4:

score: 0
Accepted
time: 187ms
memory: 5676kb

input:

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

output:

? 1881 1882
? 1880 1881
? 1880 1882
? 1879 1881
? 1879 1882
? 1879 1880
? 1878 1879
? 1878 1881
? 1878 1882
? 1878 1880
? 1877 1881
? 1877 1882
? 1877 1878
? 1877 1880
? 1876 1881
? 1876 1882
? 1876 1880
? 1876 1877
? 1876 1878
? 1875 1876
? 1875 1880
? 1875 1881
? 1875 1877
? 1874 1875
? 1874 1876
...

result:

ok OK, guesses=35431

Test #5:

score: 0
Accepted
time: 211ms
memory: 5712kb

input:

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

output:

? 1876 1877
? 1875 1876
? 1875 1877
? 1874 1875
? 1874 1876
? 1873 1874
? 1873 1875
? 1873 1876
? 1873 1877
? 1872 1874
? 1872 1875
? 1872 1873
? 1872 1876
? 1871 1874
? 1871 1875
? 1871 1872
? 1871 1876
? 1870 1873
? 1870 1874
? 1870 1875
? 1870 1876
? 1870 1871
? 1870 1872
? 1869 1873
? 1869 1874
...

result:

ok OK, guesses=35360

Test #6:

score: 0
Accepted
time: 209ms
memory: 5664kb

input:

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

output:

? 1870 1871
? 1869 1870
? 1869 1871
? 1868 1870
? 1868 1871
? 1868 1869
? 1867 1870
? 1867 1871
? 1867 1868
? 1866 1867
? 1866 1868
? 1866 1869
? 1866 1870
? 1866 1871
? 1865 1866
? 1865 1867
? 1865 1868
? 1864 1866
? 1864 1867
? 1864 1870
? 1864 1871
? 1864 1868
? 1864 1869
? 1863 1865
? 1863 1866
...

result:

ok OK, guesses=35176

Test #7:

score: 0
Accepted
time: 195ms
memory: 5684kb

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:

? 1993 1994
? 1992 1993
? 1992 1994
? 1991 1992
? 1991 1993
? 1990 1992
? 1990 1993
? 1990 1991
? 1989 1991
? 1989 1992
? 1989 1990
? 1988 1991
? 1988 1992
? 1988 1989
? 1988 1990
? 1987 1990
? 1987 1991
? 1987 1988
? 1987 1989
? 1986 1990
? 1986 1991
? 1986 1988
? 1986 1989
? 1986 1987
? 1985 1989
...

result:

ok OK, guesses=34767

Test #8:

score: 0
Accepted
time: 196ms
memory: 5748kb

input:

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

output:

? 1989 1990
? 1988 1989
? 1988 1990
? 1987 1989
? 1987 1990
? 1987 1988
? 1986 1989
? 1986 1990
? 1986 1988
? 1985 1986
? 1985 1987
? 1985 1988
? 1984 1989
? 1984 1990
? 1984 1988
? 1984 1986
? 1984 1987
? 1983 1985
? 1983 1986
? 1983 1984
? 1983 1987
? 1982 1985
? 1982 1986
? 1982 1983
? 1982 1984
...

result:

ok OK, guesses=35952

Test #9:

score: 0
Accepted
time: 203ms
memory: 5844kb

input:

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

output:

? 1980 1981
? 1979 1980
? 1979 1981
? 1978 1980
? 1978 1981
? 1978 1979
? 1977 1980
? 1977 1981
? 1977 1978
? 1977 1979
? 1976 1980
? 1976 1981
? 1976 1977
? 1975 1978
? 1975 1979
? 1975 1977
? 1975 1980
? 1974 1980
? 1974 1981
? 1974 1979
? 1974 1975
? 1973 1980
? 1973 1981
? 1973 1976
? 1973 1977
...

result:

ok OK, guesses=36990

Test #10:

score: 0
Accepted
time: 292ms
memory: 5848kb

input:

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

output:

? 1987 1988
? 1986 1987
? 1986 1988
? 1985 1986
? 1985 1987
? 1984 1985
? 1984 1986
? 1983 1984
? 1983 1985
? 1982 1983
? 1982 1984
? 1982 1987
? 1982 1988
? 1982 1985
? 1982 1986
? 1981 1983
? 1981 1984
? 1981 1982
? 1981 1987
? 1981 1988
? 1980 1985
? 1980 1986
? 1980 1987
? 1980 1988
? 1980 1981
...

result:

ok OK, guesses=37340

Test #11:

score: 0
Accepted
time: 245ms
memory: 5852kb

input:

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

output:

? 1990 1991
? 1989 1990
? 1989 1991
? 1988 1990
? 1988 1991
? 1988 1989
? 1987 1988
? 1987 1989
? 1986 1987
? 1986 1988
? 1986 1989
? 1985 1986
? 1985 1990
? 1985 1991
? 1985 1987
? 1985 1988
? 1984 1987
? 1984 1988
? 1984 1990
? 1984 1991
? 1984 1985
? 1983 1987
? 1983 1988
? 1983 1984
? 1983 1985
...

result:

ok OK, guesses=37740

Test #12:

score: 0
Accepted
time: 226ms
memory: 5900kb

input:

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

output:

? 1995 1996
? 1994 1995
? 1994 1996
? 1993 1994
? 1993 1995
? 1993 1996
? 1992 1993
? 1992 1994
? 1992 1995
? 1991 1993
? 1991 1994
? 1991 1995
? 1991 1992
? 1990 1991
? 1990 1994
? 1990 1995
? 1990 1992
? 1989 1990
? 1989 1991
? 1989 1992
? 1989 1993
? 1989 1995
? 1989 1996
? 1988 1990
? 1988 1991
...

result:

ok OK, guesses=37938

Test #13:

score: 0
Accepted
time: 181ms
memory: 5476kb

input:

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

output:

? 1991 1992
? 1990 1991
? 1989 1990
? 1989 1991
? 1988 1989
? 1988 1990
? 1987 1989
? 1987 1990
? 1987 1988
? 1986 1988
? 1986 1989
? 1986 1987
? 1985 1988
? 1985 1989
? 1985 1986
? 1985 1987
? 1984 1987
? 1984 1988
? 1984 1985
? 1984 1986
? 1983 1987
? 1983 1988
? 1983 1984
? 1983 1985
? 1982 1986
...

result:

ok OK, guesses=32755

Test #14:

score: 0
Accepted
time: 213ms
memory: 5616kb

input:

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

output:

? 1987 1988
? 1986 1987
? 1986 1988
? 1985 1987
? 1985 1988
? 1985 1986
? 1984 1987
? 1984 1988
? 1984 1985
? 1984 1986
? 1983 1987
? 1983 1988
? 1983 1985
? 1983 1986
? 1983 1984
? 1982 1983
? 1982 1984
? 1982 1985
? 1982 1986
? 1982 1987
? 1981 1987
? 1981 1988
? 1981 1982
? 1981 1986
? 1980 1987
...

result:

ok OK, guesses=35270

Test #15:

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

input:

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

output:

? 1982 1983
? 1981 1982
? 1981 1983
? 1980 1981
? 1980 1982
? 1980 1983
? 1979 1980
? 1979 1981
? 1978 1979
? 1978 1982
? 1978 1983
? 1978 1980
? 1977 1978
? 1977 1980
? 1977 1981
? 1977 1979
? 1976 1978
? 1976 1979
? 1976 1980
? 1976 1977
? 1975 1976
? 1975 1977
? 1975 1980
? 1975 1981
? 1974 1978
...

result:

ok OK, guesses=36751

Test #16:

score: 0
Accepted
time: 195ms
memory: 5768kb

input:

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

output:

? 1989 1990
? 1988 1989
? 1987 1988
? 1987 1989
? 1987 1990
? 1986 1988
? 1986 1989
? 1986 1987
? 1985 1986
? 1985 1987
? 1985 1988
? 1984 1988
? 1984 1989
? 1984 1986
? 1984 1987
? 1984 1990
? 1983 1985
? 1983 1986
? 1983 1989
? 1983 1990
? 1983 1984
? 1982 1985
? 1982 1986
? 1982 1987
? 1982 1988
...

result:

ok OK, guesses=37344

Test #17:

score: 0
Accepted
time: 234ms
memory: 5856kb

input:

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

output:

? 1988 1989
? 1987 1988
? 1987 1989
? 1986 1987
? 1986 1988
? 1985 1987
? 1985 1988
? 1985 1986
? 1985 1989
? 1984 1986
? 1984 1987
? 1984 1988
? 1984 1989
? 1983 1986
? 1983 1987
? 1983 1988
? 1983 1989
? 1983 1984
? 1982 1983
? 1982 1988
? 1982 1989
? 1982 1984
? 1982 1985
? 1981 1982
? 1981 1983
...

result:

ok OK, guesses=37811

Test #18:

score: 0
Accepted
time: 305ms
memory: 5864kb

input:

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

output:

? 1997 1998
? 1996 1997
? 1995 1996
? 1995 1997
? 1995 1998
? 1994 1996
? 1994 1997
? 1994 1995
? 1994 1998
? 1993 1994
? 1993 1995
? 1993 1997
? 1993 1998
? 1992 1994
? 1992 1995
? 1992 1993
? 1992 1997
? 1992 1998
? 1991 1992
? 1991 1996
? 1991 1997
? 1991 1995
? 1990 1994
? 1990 1995
? 1990 1996
...

result:

ok OK, guesses=37921

Test #19:

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

input:

1

output:

! 1

result:

ok OK, guesses=0

Test #20:

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

input:

2
0

output:

? 1 2
! 1 2

result:

ok OK, guesses=1

Test #21:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

2
1

output:

? 1 2
! 2 1

result:

ok OK, guesses=1

Test #22:

score: 0
Accepted
time: 183ms
memory: 5672kb

input:

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

output:

? 1996 1997
? 1995 1996
? 1995 1997
? 1994 1995
? 1994 1996
? 1993 1994
? 1993 1995
? 1993 1996
? 1992 1993
? 1992 1995
? 1992 1996
? 1992 1994
? 1991 1992
? 1991 1993
? 1991 1994
? 1991 1995
? 1991 1996
? 1990 1995
? 1990 1996
? 1990 1993
? 1990 1994
? 1990 1991
? 1990 1992
? 1989 1995
? 1989 1996
...

result:

ok OK, guesses=35290

Test #23:

score: 0
Accepted
time: 226ms
memory: 5756kb

input:

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

output:

? 1997 1998
? 1996 1997
? 1996 1998
? 1995 1997
? 1995 1998
? 1995 1996
? 1994 1995
? 1994 1997
? 1994 1998
? 1994 1996
? 1993 1997
? 1993 1998
? 1993 1995
? 1993 1996
? 1992 1997
? 1992 1998
? 1992 1995
? 1992 1996
? 1992 1993
? 1992 1994
? 1991 1992
? 1991 1993
? 1991 1994
? 1991 1995
? 1991 1996
...

result:

ok OK, guesses=35314

Test #24:

score: 0
Accepted
time: 209ms
memory: 5640kb

input:

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

output:

? 1998 1999
? 1997 1998
? 1997 1999
? 1996 1997
? 1996 1998
? 1995 1996
? 1995 1997
? 1995 1998
? 1994 1995
? 1994 1997
? 1994 1998
? 1994 1996
? 1993 1994
? 1993 1995
? 1993 1996
? 1993 1997
? 1993 1998
? 1992 1997
? 1992 1998
? 1992 1995
? 1992 1996
? 1992 1993
? 1992 1994
? 1991 1997
? 1991 1998
...

result:

ok OK, guesses=35332

Test #25:

score: 0
Accepted
time: 231ms
memory: 5716kb

input:

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

output:

? 1999 2000
? 1998 1999
? 1998 2000
? 1997 1999
? 1997 2000
? 1997 1998
? 1996 1997
? 1996 1999
? 1996 2000
? 1996 1998
? 1995 1999
? 1995 2000
? 1995 1997
? 1995 1998
? 1994 1999
? 1994 2000
? 1994 1997
? 1994 1998
? 1994 1995
? 1994 1996
? 1993 1994
? 1993 1995
? 1993 1996
? 1993 1997
? 1993 1998
...

result:

ok OK, guesses=35356