QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#800773#8823. Game: Battle of MenjisNotNotToday#WA 58ms3632kbC++231.5kb2024-12-06 15:27:242024-12-06 15:27:24

Judging History

This is the latest submission verdict.

  • [2024-12-06 15:27:24]
  • Judged
  • Verdict: WA
  • Time: 58ms
  • Memory: 3632kb
  • [2024-12-06 15:27:24]
  • Submitted

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'