QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99447 | #6303. Inversion | rgnerdplayer# | AC ✓ | 313ms | 18920kb | C++20 | 2.5kb | 2023-04-22 16:00:14 | 2023-04-22 16:00:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
// [l, r]
uniform_int_distribution<int> uni(l, r);
return uni(rng);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
auto solve = [&]() {
int n;
cin >> n;
vector<int> ord{0};
vector inv(n, vector<int>(n));
#ifdef LOCAL
vector<int> p(n);
vector f(n, vector<int>(n));
iota(p.begin(), p.end(), 0);
for (int i = 1; i < n; i++) {
swap(p[i], p[rand(0, i - 1)]);
}
for (int i = 0; i < n; i++) {
for (int j = i - 1, x = 0; j >= 0; j--) {
f[j][i] = (x += p[j] > p[i]) + f[j][i - 1];
}
}
#endif
int count = 0;
for (int i = 1; i < n; i++) {
auto ask = [&](int l, int r) {
if (l != r && r == i) {
++count;
cout << "? " << l + 1 << ' ' << r + 1 << endl;
int res;
#ifdef LOCAL
res = f[l][r] % 2;
#else
cin >> res;
#endif
return res;
} else {
return inv[l][r] % 2;
}
};
int low = 0, high = ord.size();
while (low < high) {
int mid = low + high >> 1;
int j = ord[mid];
if ((ask(j, i) ^ ask(j + 1, i) ^ ask(j, i - 1) ^ ask(j + 1, i - 1)) != 0) {
high = mid;
} else {
low = mid + 1;
}
}
for (int j = low; j < int(ord.size()); j++) {
inv[ord[j]][i] = 1;
}
for (int j = i - 1; j >= 0; j--) {
inv[j][i] += inv[j + 1][i];
}
for (int j = i - 1; j >= 0; j--) {
inv[j][i] += inv[j][i - 1];
}
ord.insert(ord.begin() + low, i);
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[ord[i]] = i;
}
cout << '!';
for (int i = 0; i < n; i++) {
cout << ' ' << ans[i] + 1;
}
cout << endl;
#ifdef LOCAL
assert(ans == p);
#endif
};
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3312kb
input:
3 0 1 0 1
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=4
Test #2:
score: 0
Accepted
time: 280ms
memory: 18836kb
input:
1993 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 4 ? 3 5 ? 4 5 ? 2 5 ? 3 5 ? 1 5 ? 2 5 ? 2 6 ? 3 6 ? 1 6 ? 2 6 ? 5 6 ? 2 7 ? 3 7 ? 6 7 ? 5 7 ? 6 7 ? 1 8 ? 2 8 ? 3 8 ? 4 8 ? 2 8 ? 3 8 ? 2 9 ? 3 9 ? 6 9 ? 7 9 ? 1 9 ? 2 9 ? 9 10 ? 6 10 ? 7 10 ? 5 10 ? 6 10 ? 7 10 ? 8 10 ? 9 11 ? 10 11 ? 5 11 ? 6 11 ? 1 11 ? 2 11 ? 11 12 ? ...
result:
ok OK, guesses=38238
Test #3:
score: 0
Accepted
time: 262ms
memory: 16968kb
input:
1887 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 3 4 ? 1 4 ? 2 4 ? 1 5 ? 2 5 ? 4 5 ? 1 6 ? 2 6 ? 4 6 ? 5 6 ? 5 6 ? 5 7 ? 6 7 ? 3 7 ? 4 7 ? 1 7 ? 2 7 ? 7 8 ? 6 8 ? 7 8 ? 4 8 ? 5 8 ? 5 9 ? 6 9 ? 8 9 ? 4 9 ? 5 9 ? 5 10 ? 6 10 ? 1 10 ? 2 10 ? 3 10 ? 4 10 ? 2 10 ? 3 10 ? 5 11 ? 6 11 ? 9 11 ? 10 11 ? 8 11 ? 9 11 ? 6 11 ? 7 11 ?...
result:
ok OK, guesses=35786
Test #4:
score: 0
Accepted
time: 262ms
memory: 16932kb
input:
1882 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 2 4 ? 3 4 ? 1 5 ? 2 5 ? 2 5 ? 3 5 ? 4 5 ? 2 6 ? 3 6 ? 3 6 ? 4 6 ? 1 6 ? 2 6 ? 1 7 ? 2 7 ? 3 7 ? 4 7 ? 6 7 ? 1 8 ? 2 8 ? 5 8 ? 6 8 ? 4 8 ? 5 8 ? 1 9 ? 2 9 ? 5 9 ? 6 9 ? 4 9 ? 5 9 ? 8 9 ? 2 10 ? 3 10 ? 6 10 ? 7 10 ? 3 10 ? 4 10 ? 1 11 ? 2 11 ? 4 11 ? 5 11 ? 2 11 ? 3 11 ...
result:
ok OK, guesses=35742
Test #5:
score: 0
Accepted
time: 278ms
memory: 17148kb
input:
1877 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 2 4 ? 3 4 ? 4 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 ? 4 8 ? 5 8 ? 1 8 ? 2 8 ? 8 9 ? 4 9 ? 5 9 ? 2 9 ? 3 9 ? 8 10 ? 9 10 ? 2 10 ? 3 10 ? 9 10 ? 1 11 ? 2 11 ? 3 11 ? 4 11 ? 5 11 ? 6 11 ? 8 12 ? 9 12 ? 11 ...
result:
ok OK, guesses=35536
Test #6:
score: 0
Accepted
time: 186ms
memory: 16676kb
input:
1871 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 3 5 ? 4 5 ? 1 5 ? 2 5 ? 3 6 ? 4 6 ? 2 6 ? 3 6 ? 4 6 ? 5 6 ? 3 7 ? 4 7 ? 5 7 ? 6 7 ? 1 7 ? 2 7 ? 3 8 ? 4 8 ? 4 8 ? 5 8 ? 2 8 ? 3 8 ? 3 9 ? 4 9 ? 1 9 ? 2 9 ? 5 9 ? 6 9 ? 3 10 ? 4 10 ? 8 10 ? 9 10 ? 2 10 ? 3 10 ? 3 11 ? 4 11 ? 8 11 ? 9 11 ? 4 11 ? 5 11 ? 6 11...
result:
ok OK, guesses=35460
Test #7:
score: 0
Accepted
time: 170ms
memory: 18572kb
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 ? 2 4 ? 3 4 ? 3 4 ? 3 5 ? 4 5 ? 4 5 ? 3 6 ? 4 6 ? 5 6 ? 4 7 ? 5 7 ? 6 7 ? 4 8 ? 5 8 ? 6 8 ? 7 8 ? 7 8 ? 5 9 ? 6 9 ? 7 9 ? 8 9 ? 8 9 ? 5 10 ? 6 10 ? 8 10 ? 9 10 ? 9 10 ? 6 11 ? 7 11 ? 9 11 ? 10 11 ? 10 11 ? 6 12 ? 7 12 ? 9 12 ? 10 12 ? 11 12 ? 7 13 ? 8 13 ? 10 13 ? 11 13 ? 12 13 ? 7 14 ? ...
result:
ok OK, guesses=33815
Test #8:
score: 0
Accepted
time: 205ms
memory: 18656kb
input:
1990 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 1 4 ? 2 4 ? 2 5 ? 3 5 ? 1 5 ? 2 5 ? 5 6 ? 3 6 ? 4 6 ? 2 7 ? 3 7 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 7 8 ? 1 8 ? 2 8 ? 5 8 ? 6 8 ? 7 9 ? 8 9 ? 3 9 ? 4 9 ? 2 9 ? 3 9 ? 7 10 ? 8 10 ? 3 10 ? 4 10 ? 6 10 ? 7 10 ? 2 11 ? 3 11 ? 10 11 ? 6 11 ? 7 11 ? 2 12 ? 3 12 ? 10 12 ? 11 12 ? 11 12 ? 9 ...
result:
ok OK, guesses=36474
Test #9:
score: 0
Accepted
time: 233ms
memory: 18512kb
input:
1981 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 3 5 ? 4 5 ? 2 5 ? 3 5 ? 4 5 ? 2 6 ? 3 6 ? 1 6 ? 2 6 ? 3 7 ? 4 7 ? 5 7 ? 6 7 ? 4 7 ? 5 7 ? 2 8 ? 3 8 ? 4 8 ? 5 8 ? 7 8 ? 2 9 ? 3 9 ? 4 9 ? 5 9 ? 7 9 ? 8 9 ? 8 9 ? 5 10 ? 6 10 ? 7 10 ? 8 10 ? 8 10 ? 9 10 ? 9 10 ? 5 11 ? 6 11 ? 8 11 ? 9 11 ? 4 11 ? 5 11 ? 7 1...
result:
ok OK, guesses=37120
Test #10:
score: 0
Accepted
time: 213ms
memory: 18516kb
input:
1988 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 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 ? 1 3 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 4 5 ? 3 5 ? 4 5 ? 1 5 ? 2 5 ? 3 6 ? 4 6 ? 2 6 ? 3 6 ? 4 7 ? 5 7 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 3 8 ? 4 8 ? 7 8 ? 1 8 ? 2 8 ? 3 9 ? 4 9 ? 8 9 ? 1 9 ? 2 9 ? 1 10 ? 2 10 ? 2 10 ? 3 10 ? 6 10 ? 7 10 ? 3 11 ? 4 11 ? 6 11 ? 7 11 ? 10 11 ? 3 12 ? 4 12 ? 8 12 ? 9 12 ? ...
result:
ok OK, guesses=37548
Test #11:
score: 0
Accepted
time: 255ms
memory: 18564kb
input:
1991 0 1 1 1 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 4 5 ? 3 5 ? 4 5 ? 5 6 ? 3 6 ? 4 6 ? 1 6 ? 2 6 ? 5 7 ? 6 7 ? 2 7 ? 3 7 ? 4 7 ? 5 7 ? 5 8 ? 6 8 ? 4 8 ? 5 8 ? 2 8 ? 3 8 ? 7 9 ? 8 9 ? 3 9 ? 4 9 ? 6 9 ? 7 9 ? 5 10 ? 6 10 ? 2 10 ? 3 10 ? 4 10 ? 5 10 ? 7 10 ? 8 10 ? 7 11 ? 8 11 ? 9 11 ? 10 11 ? 5 11 ? 6 11 ? 3...
result:
ok OK, guesses=37935
Test #12:
score: 0
Accepted
time: 240ms
memory: 18780kb
input:
1996 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 2 4 ? 3 4 ? 4 5 ? 2 5 ? 3 5 ? 4 6 ? 5 6 ? 2 6 ? 3 6 ? 5 6 ? 5 7 ? 6 7 ? 2 7 ? 3 7 ? 6 7 ? 5 8 ? 6 8 ? 1 8 ? 2 8 ? 3 8 ? 4 8 ? 5 9 ? 6 9 ? 6 9 ? 7 9 ? 2 9 ? 3 9 ? 5 10 ? 6 10 ? 1 10 ? 2 10 ? 4 10 ? 5 10 ? 5 11 ? 6 11 ? 1 11 ? 2 11 ? 10 11 ? 4 11 ? 5 11 ? 10 12 ? ...
result:
ok OK, guesses=38191
Test #13:
score: 0
Accepted
time: 280ms
memory: 18496kb
input:
1992 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 2 4 ? 3 4 ? 3 4 ? 2 5 ? 3 5 ? 3 5 ? 4 5 ? 4 5 ? 3 6 ? 4 6 ? 4 6 ? 5 6 ? 5 6 ? 3 7 ? 4 7 ? 5 7 ? 6 7 ? 6 7 ? 4 8 ? 5 8 ? 6 8 ? 7 8 ? 7 8 ? 4 9 ? 5 9 ? 6 9 ? 7 9 ? 7 9 ? 8 9 ? 8 9 ? 5 10 ? 6 10 ? 7 10 ? 8 10 ? 8 10 ? 9 10 ? 9 10 ? 5 11 ? 6 11 ? 8 11 ? 9 11 ? 9 11 ? 10 11 ? 10...
result:
ok OK, guesses=37739
Test #14:
score: 0
Accepted
time: 286ms
memory: 18516kb
input:
1988 1 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 3 5 ? 4 5 ? 1 5 ? 2 5 ? 3 6 ? 4 6 ? 2 6 ? 3 6 ? 3 7 ? 4 7 ? 5 7 ? 6 7 ? 1 7 ? 2 7 ? 3 8 ? 4 8 ? 7 8 ? 5 8 ? 6 8 ? 1 9 ? 2 9 ? 6 9 ? 7 9 ? 2 9 ? 3 9 ? 4 9 ? 5 9 ? 3 10 ? 4 10 ? 8 10 ? 9 10 ? 7 10 ? 8 10 ? 1 10 ? 2 10 ? 10 11 ? 2 11 ? 3 11 ? 4 11 ? 5 11 ? 9 ...
result:
ok OK, guesses=38142
Test #15:
score: 0
Accepted
time: 222ms
memory: 18552kb
input:
1983 1 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 2 4 ? 3 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 2 5 ? 2 6 ? 3 6 ? 4 6 ? 5 6 ? 2 7 ? 3 7 ? 4 7 ? 5 7 ? 3 7 ? 4 7 ? 6 8 ? 7 8 ? 3 8 ? 4 8 ? 4 8 ? 5 8 ? 6 9 ? 7 9 ? 8 9 ? 3 9 ? 4 9 ? 7 9 ? 8 9 ? 4 10 ? 5 10 ? 3 10 ? 4 10 ? 8 10 ? 9 10 ? 4 11 ? 5 11 ? 3 11 ? 4 11 ? 8 11 ? 9 11 ? 11 12 ? 2 ...
result:
ok OK, guesses=38067
Test #16:
score: 0
Accepted
time: 313ms
memory: 18584kb
input:
1990 1 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 2 4 ? 3 4 ? 1 5 ? 2 5 ? 4 5 ? 5 6 ? 3 6 ? 4 6 ? 1 6 ? 2 6 ? 6 7 ? 4 7 ? 5 7 ? 2 7 ? 3 7 ? 5 8 ? 6 8 ? 7 8 ? 4 8 ? 5 8 ? 5 9 ? 6 9 ? 1 9 ? 2 9 ? 6 9 ? 7 9 ? 5 10 ? 6 10 ? 1 10 ? 2 10 ? 9 10 ? 6 10 ? 7 10 ? 10 11 ? 8 11 ? 9 11 ? 7 11 ? 8 11 ? 2 11 ? 3 11 ? 5 12 ? 6 12 ?...
result:
ok OK, guesses=38276
Test #17:
score: 0
Accepted
time: 275ms
memory: 18608kb
input:
1989 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 3 ? 3 4 ? 1 4 ? 2 4 ? 1 5 ? 2 5 ? 4 5 ? 1 6 ? 2 6 ? 3 6 ? 4 6 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 1 8 ? 2 8 ? 5 8 ? 6 8 ? 7 8 ? 4 9 ? 5 9 ? 7 9 ? 8 9 ? 5 9 ? 6 9 ? 4 10 ? 5 10 ? 7 10 ? 8 10 ? 9 10 ? 5 10 ? 6 10 ? 5 11 ? 6 11 ? 6 11 ? 7 11 ? 4 11 ? 5 11 ? 11 12 ? 6 12 ? 7 12 ? 3 12 ? 4 12...
result:
ok OK, guesses=38092
Test #18:
score: 0
Accepted
time: 172ms
memory: 18920kb
input:
1998 0 1 0 1 0 0 0 1 0 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 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 0 1 0...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ? 1 4 ? 2 4 ? 3 4 ? 1 5 ? 2 5 ? 4 5 ? 3 5 ? 4 5 ? 4 6 ? 5 6 ? 5 6 ? 3 6 ? 4 6 ? 4 7 ? 5 7 ? 2 7 ? 3 7 ? 4 8 ? 5 8 ? 2 8 ? 3 8 ? 7 8 ? 1 9 ? 2 9 ? 8 9 ? 2 9 ? 3 9 ? 1 10 ? 2 10 ? 8 10 ? 9 10 ? 9 10 ? 2 11 ? 3 11 ? 5 11 ? 6 11 ? 1 11 ? 2 11 ? 11 12 ? 10 12 ? 11 12 ? 7 12 ? 8 12...
result:
ok OK, guesses=38262
Test #19:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
1
output:
! 1
result:
ok OK, guesses=0
Test #20:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
2 0
output:
? 1 2 ! 1 2
result:
ok OK, guesses=1
Test #21:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
2 1
output:
? 1 2 ! 2 1
result:
ok OK, guesses=1
Test #22:
score: 0
Accepted
time: 201ms
memory: 18772kb
input:
1997 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 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 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 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 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1...
output:
? 1 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 ? 3 6 ? 4 6 ? 6 7 ? 5 7 ? 6 7 ? 6 8 ? 7 8 ? 5 8 ? 6 8 ? 3 8 ? 4 8 ? 3 9 ? 4 9 ? 5 9 ? 6 9 ? 7 9 ? 8 9 ? 3 10 ? 4 10 ? 7 10 ? 8 10 ? 5 10 ? 6 10 ? 8 11 ? 9 11 ? 7 11 ? 8 11 ? 9 11 ? 10 11 ? 8 12 ? 9 12 ? 7 12 ? 8 12 ?...
result:
ok OK, guesses=35867
Test #23:
score: 0
Accepted
time: 195ms
memory: 18844kb
input:
1998 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 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 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 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 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1...
output:
? 1 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 ? 3 6 ? 4 6 ? 6 7 ? 5 7 ? 6 7 ? 6 8 ? 7 8 ? 5 8 ? 6 8 ? 3 8 ? 4 8 ? 3 9 ? 4 9 ? 5 9 ? 6 9 ? 7 9 ? 8 9 ? 3 10 ? 4 10 ? 7 10 ? 8 10 ? 5 10 ? 6 10 ? 8 11 ? 9 11 ? 7 11 ? 8 11 ? 9 11 ? 10 11 ? 8 12 ? 9 12 ? 7 12 ? 8 12 ?...
result:
ok OK, guesses=35888
Test #24:
score: 0
Accepted
time: 237ms
memory: 18836kb
input:
1999 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 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 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 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 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1...
output:
? 1 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 ? 3 6 ? 4 6 ? 6 7 ? 5 7 ? 6 7 ? 6 8 ? 7 8 ? 5 8 ? 6 8 ? 3 8 ? 4 8 ? 3 9 ? 4 9 ? 5 9 ? 6 9 ? 7 9 ? 8 9 ? 3 10 ? 4 10 ? 7 10 ? 8 10 ? 5 10 ? 6 10 ? 8 11 ? 9 11 ? 7 11 ? 8 11 ? 9 11 ? 10 11 ? 8 12 ? 9 12 ? 7 12 ? 8 12 ?...
result:
ok OK, guesses=35907
Test #25:
score: 0
Accepted
time: 243ms
memory: 18800kb
input:
2000 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 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 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 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 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1...
output:
? 1 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 ? 3 6 ? 4 6 ? 6 7 ? 5 7 ? 6 7 ? 6 8 ? 7 8 ? 5 8 ? 6 8 ? 3 8 ? 4 8 ? 3 9 ? 4 9 ? 5 9 ? 6 9 ? 7 9 ? 8 9 ? 3 10 ? 4 10 ? 7 10 ? 8 10 ? 5 10 ? 6 10 ? 8 11 ? 9 11 ? 7 11 ? 8 11 ? 9 11 ? 10 11 ? 8 12 ? 9 12 ? 7 12 ? 8 12 ?...
result:
ok OK, guesses=35928