QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#668784 | #8719. 后继 | ucup-team4479# | WA | 0ms | 13880kb | C++14 | 1.5kb | 2024-10-23 15:56:35 | 2024-10-23 15:56:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int a[N], dfn[N * 30], col[N * 30], siz[N * 30], flag[40], id[N];
int n, m, tot = 1, rt = 1, tim = 0, ans = 0;
int trie[N * 30][2];
void insert(int &u, int k, int x, int c) {
if (!u) u = ++tot;
if (k == -1) {
col[u] = c;
id[c] = u;
return;
}
bool f = (x >> k) & 1;
insert(trie[u][f], k - 1, x, c);
if (trie[u][0] && trie[u][1]) flag[k] = u;
}
void dfs(int u) {
dfn[u] = ++tim;
siz[u] = 1;
for (int i = 0; i < 2; ++i) {
int v = trie[u][i];
if (!v) continue;
dfs(v);
siz[u] += siz[v];
}
}
int query(int u, int k) {
if (col[u]) return col[u];
if (!trie[u][0]) return query(trie[u][1], k - 1);
if (!trie[u][1]) return query(trie[u][0], k - 1);
bool f = (ans >> k) & 1;
return query(trie[u][f ^ 1], k - 1);
}
void solve() {
ans = 0;
for (int i = 0; i < 30; ++i) {
if (!flag[i]) continue;
int u = query(flag[i], i), v;
cout << "? " << u << endl;
cin >> v;
v = v == -1 ? -1 : id[v];
if (v >= dfn[flag[i]] && v <= dfn[flag[i]] + siz[flag[i]] - 1) {
ans = ans ^ (1 << i);
}
}
cout << "! " << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
insert(rt, 29, a[i], i);
}
dfs(1);
while (m--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 13880kb
input:
5 1 1 2 3 4 5 4 1 -1
output:
? 5 ? 2 ? 4 ! 3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11872kb
input:
1 1 0
output:
! 0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 13796kb
input:
10 10 380864879 387438357 21484978 21099484 375657510 23189485 24467021 379687119 386094773 15156199 -1 9 4 2 -1 10 10 9 4 5 10 1 4 9 10 3 10 5 4 9 -1 5 -1 10 10 9 4 5 10 1 10 9 4 5 10 1 6 8 10 5 10 8 4 9 -1 5 -1 10 4 10 7 1 7 2 8 -1 4 5 8 -1
output:
? 3 ? 2 ? 6 ? 8 ? 3 ? 9 ! 271581184 ? 3 ? 2 ? 6 ? 8 ? 3 ? 9 ! 279969792 ? 3 ? 2 ? 6 ? 8 ? 6 ? 9 ! 269484032 ? 3 ? 2 ? 6 ? 8 ? 6 ? 9 ! 277872640 ? 3 ? 2 ? 6 ? 8 ? 3 ? 9 ! 279969792 ? 3 ? 2 ? 6 ? 8 ? 3 ? 9 ! 279969792 ? 3 ? 2 ? 7 ? 1 ? 7 ? 2 ! 276824064 ? 3 ? 2 ? 6 ? 8 ? 6 ? 9 ! 277872640 ? 3 ? 2 ? 6 ...
result:
wrong answer 2nd numbers differ - expected: '296747008', found: '279969792'