QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#417414 | #8719. 后继 | hhhhyf | WA | 47ms | 3804kb | C++20 | 1.7kb | 2024-05-22 18:32:06 | 2024-05-22 18:32:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
const int N = 400010, M = 30;
int ch[N * M][M], idx, a[N], pre[N * M];
int ed[N * M], node[M];
void insert (int x, int v) {
int p = 0;
for (int i = M - 1, s = 0; i >= 0; i --) {
int j = x >> i & 1;
s |= j << i;
int& u = ch[p][j];
if (!u) {
u = ++ idx;
pre[u] = s;
}
if (node[i] == 0 && ch[p][0] && ch[p][1]) {
node[i] = p;
}
p = u;
}
ed[p] = v;
}
int query (int x) {
cout << "? " << x << endl;
int res;
cin >> res;
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
int x;
cin >> x;
a[i] = x;
insert(x, i);
}
while (m --) {
int ans = 0;
for (int i = 0; i < M; i ++) {
int& x = node[i];
if (!x) continue;
function<int(int, int)> get_max = [&](int p, int j) {
if (j == -1) {
return ed[p];
}
if (!ch[p][1]) {
return get_max(ch[p][0], j - 1);
}
if (!ch[p][0]) {
return get_max(ch[p][1], j - 1);
}
if (ans >> j & 1 ^ 1) {
return get_max(ch[p][1], j - 1);
}
return get_max(ch[p][0], j - 1);
};
int p = get_max(ch[x][0], i - 1);
int q = query(p);
if (q == -1 || (a[q] ^ pre[ch[x][1]]) >= (1 << i)) {
ans |= 1 << i;
}
}
cout << "! " << ans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3504kb
input:
5 1 1 2 3 4 5 1 5 5
output:
? 2 ? 1 ? 1 ! 3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
1 1 0
output:
! 0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
10 10 380864879 387438357 21484978 21099484 375657510 23189485 24467021 379687119 386094773 15156199 3 4 -1 1 2 -1 3 4 10 7 7 -1 7 10 7 1 3 -1 7 -1 7 2 2 -1 3 4 10 -1 -1 2 3 4 10 -1 -1 2 3 7 6 4 4 -1 7 -1 7 2 2 -1 6 7 6 8 9 -1 3 7 8 9 9 8
output:
? 4 ? 6 ? 3 ? 5 ? 8 ? 3 ! 271581184 ? 4 ? 6 ? 3 ? 5 ? 5 ? 10 ! 296747008 ? 4 ? 6 ? 4 ? 5 ? 8 ? 10 ! 286523392 ? 4 ? 6 ? 4 ? 5 ? 5 ? 6 ! 278134784 ? 4 ? 6 ? 3 ? 5 ? 5 ? 10 ! 28311552 ? 4 ? 6 ? 3 ? 5 ? 5 ? 10 ! 28311552 ? 4 ? 6 ? 3 ? 5 ? 5 ? 10 ! 293601280 ? 4 ? 6 ? 4 ? 5 ? 5 ? 6 ! 278134784 ? 4 ? 6 ?...
result:
ok 10 numbers
Test #4:
score: -100
Wrong Answer
time: 47ms
memory: 3804kb
input:
100 3000 416322873 449728250 688705913 946343465 16202884 153238658 573284215 724198910 577719053 868106680 951494055 942341618 190594266 331719623 856324110 977865755 151782935 163752541 1565918 870244322 299691610 37854919 198293342 152446496 549402023 869857831 869628458 573984494 162791133 94423...
output:
? 11 ? 58 ? 88 ? 26 ? 27 ? 17 ? 17 ? 7 ? 72 ? 78 ? 19 ? 44 ! 184027136 ? 11 ? 58 ? 88 ? 26 ? 27 ? 17 ? 17 ? 7 ? 4 ? 78 ? 55 ? 44 ! 445644800 ? 11 ? 58 ? 88 ? 26 ? 27 ? 17 ? 24 ? 28 ? 81 ? 78 ? 57 ? 92 ! 145555456 ? 11 ? 58 ? 88 ? 26 ? 27 ? 17 ? 17 ? 7 ? 30 ? 78 ? 77 ? 44 ! 179914752 ? 11 ? 58 ? 88 ?...
result:
wrong answer 5th numbers differ - expected: '543703040', found: '6832128'