# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
151466387 |
Practice:
LMXZ |
1658D2
- 60
|
C++17 (GCC 7-32)
|
Accepted
|
264 ms
|
10344 KB
|
2022-03-31 07:45:51 |
2022-03-31 07:45:50 |
|
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
//#undef LOCAL
#ifdef LOCAL
#define debug(x) cout << #x << "=" << (x) << endl
#define debugv(v) \
cout << #v << "="; \
for (auto _ : v) \
cout << _ << " "; \
cout << endl;
#else
#define assert(x)
#define debug(x)
#define debugv(v)
#endif
using namespace std;
const int N = 1 << 17;
vector sum(19, vector<int>(N));
int ssum(int b, int l, int r) {
return sum[b][r] - (l ? sum[b][l - 1] : 0);
}
void testc() {
int l, r;
cin >> l >> r;
int n = r - l + 1;
vector a(n, 0);
for (auto& i : a)
cin >> i;
int h = 0, ans = 0, flg = -1;
for (int i = 18, j = (1 << 18); i >= 0; i--, j >>= 1) {
int c1 = 0;
for (int x : a)
if (x & j)
c1++;
if (c1 == 0 || c1 == n) {
if (c1 != ssum(i, l, r))
ans ^= j;
if (ssum(i, l, r) == n)
h ^= j;
} else {
h ^= j;
flg = j;
if (c1 != ssum(i, l, r))
ans ^= j;
break;
}
}
if (flg == -1)
return void(cout << ans);
debug(h);
vector s(2, vector(19, 0));
for (int i = 0, j = 1; j < flg; i++, j <<= 1) {
for (int x : a) {
if (x & j)
s[((x ^ ans) & flg) ? 1 : 0][i]++;
}
}
for (int i = 0; (1 << i) < flg; i++) {
if (s[0][i] != ssum(i, l, h - 1) || s[1][i] != ssum(i, h, r))
ans ^= 1 << i;
}
cout << ans;
#ifdef LOCAL
cout << endl;
map<int, int> mp;
for (int i : a)
mp[i ^ ans]++;
for (auto [k, v] : mp) {
assert(l <= k && k <= r && v == 1);
}
#endif
}
void init() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#endif //! LOCAL
for (int i = 0; i < N; i++) {
for (int j = 0, k = 1; k <= i; j++, k <<= 1)
if (i & k) {
sum[j][i]++;
}
}
for (auto& v : sum) {
int n = v.size();
for (int i = 1; i < n; i++)
v[i] += v[i - 1];
}
}
int main() {
init();
int t = 1;
cin >> t;
while (t--) {
testc();
if (t)
cout << endl;
}
return 0;
}
Click to see test details