QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#455929#8823. Game: Battle of Menjishos_lyricTL 179ms4044kbC++142.1kb2024-06-27 02:20:312024-06-27 02:20:32

Judging History

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

  • [2024-06-27 11:29:18]
  • hack成功,自动添加数据
  • (/hack/704)
  • [2024-06-27 02:20:32]
  • 评测
  • 测评结果:TL
  • 用时:179ms
  • 内存:4044kb
  • [2024-06-27 02:20:31]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int N;
Int K;
vector<Int> A;

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%lld", &N, &K);
    A.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &A[i]);
    }
    
    Int base = 0;
    for (int i = 0; i < N; ++i) {
      base ^= A[i];
    }
    
    multiset<Int> ds;
    for (int i = 0; i < N; ++i) {
      if (A[i] > 0) ds.insert(A[i] ^ (A[i] - 1));
    }
    
    Int mx = -1;
    for (int i = 0; i < N; ++i) {
      if (A[i] > 0) ds.erase(ds.find(A[i] ^ (A[i] - 1)));
      Int mn = base;
      for (const Int d : ds) {
        Int t = base;
        t ^= A[i] ^ (A[i] + 1);
        t ^= d;
        chmin(mn, t);
      }
      chmax(mx, mn);
      if (A[i] > 0) ds.insert(A[i] ^ (A[i] - 1));
    }
    printf("%lld\n", mx);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}


详细

Test #1:

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

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: 48ms
memory: 3684kb

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: 179ms
memory: 3768kb

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
Time Limit Exceeded

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:


result: