QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#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

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

[2024-10-23 15:56:49]
评测

测评结果：WA
用时：0ms
内存：13880kb

查看

[2024-10-23 15:56:35]
提交

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;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 13880kb

input:

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'