-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEcho.cpp
More file actions
56 lines (44 loc) · 1022 Bytes
/
Copy pathEcho.cpp
File metadata and controls
56 lines (44 loc) · 1022 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
struct LinearBasis {
long long basis[31];
LinearBasis() {
memset(basis, 0, sizeof(basis));
}
void insert(long long x) {
for (int i = 30; i >= 0; i--) {
if (!(x & (1LL << i))) continue;
if (!basis[i]) {
basis[i] = x;
return;
}
x ^= basis[i];
}
}
long long minimize(long long x) {
for (int i = 30; i >= 0; i--) {
if (basis[i])
x = min(x, x ^ basis[i]);
}
return x;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int N, P;
cin >> N >> P;
P--; // 0-index
vector<long long> A(N);
for (auto &x : A) cin >> x;
LinearBasis lb;
// insert ALL elements
for (auto x : A) {
lb.insert(x);
}
cout << lb.minimize(A[P]) << "\n";
}
}