QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463775#8823. Game: Battle of MenjisGenshinImpactsFault#WA 87ms3648kbC++201.6kb2024-07-05 14:07:472024-07-05 14:07:48

Judging History

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

  • [2024-07-05 14:07:48]
  • 评测
  • 测评结果:WA
  • 用时:87ms
  • 内存:3648kb
  • [2024-07-05 14:07:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k, a[N];
int ch[N * 31][2], cnt[N * 31], tot;
int ans, sum;

void insert(int x, int w) {
    int u = 1; cnt[u] += w;
    for(int i = 30; ~i; i--) {
        int c = (x >> i) & 1;
        if(!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c], cnt[u] += w;
    }
}
int ask(int x) {
    int res = 0, u = 1;
    for(int i = 30; ~i; i--) {
        int c = (x >> i) & 1;
        if(ch[u][c] && cnt[ch[u][c]]) u = ch[u][c];
        else u = ch[u][c ^ 1], res += (1 << i);
    }
    return res;
}
void solve() {
    cin >> n >> k;
    ans = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], ans ^= a[i];
    sum = ans; ans = 0;
    if(n == 1) {
        cout << ans << "\n"; return ;
    }
    for(int i = 1; i <= tot; i++) {
        memset(ch[i], 0, sizeof(ch[i]));
        cnt[i] = 0;
    }
    tot = 1;
    for(int i = 1; i <= n; i++) {
        if(a[i] > 0) {
            insert(a[i] ^ (a[i] - 1), 1);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] > 0) {
            insert(a[i] ^ (a[i] - 1), -1);
        }
        insert(a[i] ^ (a[i] + 1), 1);
        ans = max(ans, ask(sum ^ a[i] ^ (a[i] + 1)));
        insert(a[i] ^ (a[i] + 1), -1);
        // cout << "### " << i << " : " << ask(sum ^ a[i] ^ (a[i] + 1)) << "\n";
        if(a[i] > 0) {
            insert(a[i] ^ (a[i] - 1), 1);
        }
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(0); cin.tie(nullptr);
    int T; cin >> T;
    for(; T; --T) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

4
2 3
1 1
4 4
0 0 0 0
4 1
1 2 4 8
13 5
1 1 4 5 1 4 1 9 1 9 8 1 0

output:

0
0
9
11

result:

ok 4 number(s): "0 0 9 11"

Test #2:

score: -100
Wrong Answer
time: 87ms
memory: 3648kb

input:

100000
1 5
0
4 5
4 4 3 5
5 2
0 1 7 5 4
4 1
6 4 4 4
1 5
3
2 2
1 1
3 1
5 4 0
2 4
0 3
2 2
1 7
3 1
2 1 6
2 4
5 1
3 1
3 7 0
4 4
7 5 4 4
3 3
1 1 5
1 3
3
3 2
3 7 4
4 1
3 1 0 5
5 3
6 2 3 6 3
3 1
2 6 6
4 4
5 4 1 3
2 1
4 4
4 5
0 1 6 5
4 5
0 7 7 5
2 4
4 0
5 1
7 0 2 6 0
3 4
5 2 3
2 3
4 3
3 2
1 0 1
2 2
6 5
5 1
6...

output:

0
2
7
2
0
0
1
3
6
5
4
4
2
5
0
0
7
2
0
3
0
2
5
4
3
4
7
0
3
2
4
4
4
2
4
6
1
3
2
7
4
0
4
6
2
4
0
0
7
0
2
2
1
0
6
0
0
0
1
0
1
3
3
0
0
1
5
5
5
1
6
4
1
2
0
0
1
4
3
6
7
7
0
1
0
0
0
4
0
4
7
0
7
0
6
0
5
4
7
4
0
6
4
0
3
4
7
5
4
4
3
6
1
0
5
4
2
1
1
0
0
0
0
0
1
0
0
0
0
4
6
3
1
0
5
0
0
0
3
0
0
4
0
0
1
2
0
7
6
7
...

result:

wrong answer 5th numbers differ - expected: '3', found: '0'