QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#800773 | #8823. Game: Battle of Menjis | NotNotToday# | WA | 58ms | 3632kb | C++23 | 1.5kb | 2024-12-06 15:27:24 | 2024-12-06 15:27:24 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <vector>
#include <cctype>
#include <cassert>
#include <random>
#include <map>
#define ld long double
#define pb push_back
#define all(a) a.begin(), a.end()
using namespace std;
const int INF = 1e9;
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int base_res = 0;
for (int i = 0; i < n; i++) {
base_res ^= a[i];
}
int ans = 0;
vector<int> cnt(30);
for (int i = 0; i < n; i++) {
if (a[i] != 0) {
cnt[__builtin_ctz(a[i])]++;
}
}
for (int i = 0; i < n; i++) {
int res = base_res ^ a[i] ^ (a[i] + 1);
if (a[i] != 0) cnt[__builtin_ctz(a[i])]--;
cnt[__builtin_ctz(a[i] + 1)]++;
int best_result = INF;
for (int j = 0; j < 30; j++) {
if (cnt[j] > 0) {
best_result = min(best_result, res ^ ((1 << (j + 1)) - 1));
}
}
ans = max(ans, best_result);
if (a[i] != 0) cnt[__builtin_ctz(a[i])]++;
cnt[__builtin_ctz(a[i] + 1)]--;
}
cout << ans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
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: 0
Accepted
time: 58ms
memory: 3632kb
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 3 0 1 3 6 5 4 4 2 5 3 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 7 4 6 2 4 4 3 7 0 2 2 1 0 6 7 0 0 1 7 1 3 3 6 2 1 5 5 5 1 6 4 1 2 0 7 1 4 3 6 7 7 0 1 7 0 0 4 0 4 7 7 7 4 6 2 5 4 7 4 1 6 4 4 3 4 7 5 4 4 3 6 1 2 5 4 2 1 1 0 0 0 0 6 1 3 4 0 1 4 6 3 1 3 5 1 0 6 3 2 1 4 5 2 1 2 2 7 6 7 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 37ms
memory: 3632kb
input:
10000 45 41 124 126 8 59 3 89 75 2 88 65 17 107 90 92 113 103 122 7 87 89 61 78 4 27 61 117 9 122 40 114 80 54 63 111 19 4 89 77 99 12 93 28 34 106 75 47 50 49 52 96 35 99 61 126 80 122 33 96 67 99 44 29 4 126 64 0 111 31 84 8 52 16 112 103 85 13 50 4 42 70 76 121 96 96 3 21 118 116 50 90 63 15 69 0...
output:
55 7 110 84 12 57 76 48 4 76 8 97 37 18 72 6 37 70 20 17 55 31 118 118 3 78 67 62 18 97 14 24 86 49 81 33 84 95 78 47 80 51 64 55 86 105 96 64 67 29 14 42 94 49 34 78 27 5 8 59 68 43 23 108 78 67 99 84 109 5 75 29 48 42 102 37 87 68 81 87 101 111 10 34 106 90 52 8 67 37 36 9 71 76 79 108 25 49 107 9...
result:
ok 10000 numbers
Test #4:
score: -100
Wrong Answer
time: 40ms
memory: 3612kb
input:
100 4991 710173979 194350399 308253661 453535140 859535540 237118582 491883070 203713206 876045568 179614490 762427255 600586096 195805957 619372254 837564280 46030125 818656915 624958658 579965169 315157532 507369398 223649057 730321515 87001797 103914474 146001643 169828188 694735418 411534273 158...
output:
895973929 644710414 718127976 764287680 427180528 89428087 633652199 202995551 1000000000 492532509 856424472 740558823 71451464 522956950 559048723 352180449 357679270 737527068 105530653 703884103 744126411 991785031 92210383 423071396 825321389 911136722 406765701 757424811 1000000000 312227835 6...
result:
wrong answer 9th numbers differ - expected: '1019972853', found: '1000000000'