//xorsum.cpp created at 03/04/21 10:30:22
#include <bits/stdc++.h>
using namespace std;
#define LB lower_bound
const int MN = 1000006;
const int LG = 23;
int N;
int A[MN];
int val[MN];
int psum[(1 << (LG + 1)) + 1];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i=0; i<N; ++i) {
cin >> A[i];
}
sort(A, A+N);
int ans = 0;
for (int i=0; i<LG; ++i) {
fill(psum, psum + (1 << (i+2)) + 1, 0);
for (int j=0; j<N; ++j) {
++psum[(A[j] & ((1 << (i + 1)) - 1)) + 1]; // add 1 for easy indexing stuff
}
for (int j=1; j<=(1 << (i+2)); ++j) {
psum[j] += psum[j - 1];
}
// range [2^i, 2^(i+1)) and [2^(i+1) + 2^i, 2^(i+2))
int ct = 0;
for (int j=0; j<N; ++j) {
const int cur = A[j] & ((1 << (i + 1)) - 1);
const int lo1 = (1 << i) - cur;
ct += psum[(1 << (i + 1)) - cur] - psum[lo1 < 0 ? 0 : lo1] +
psum[(1 << (i + 2)) - cur] - psum[(1 << (i + 1)) + lo1] +
(((A[j] << 1) >> i) & 1);
}
ans |= (ct & 2) << (i == 0 ? 0 : i-1);
}
for (int i=LG; i<=30; ++i) {
for (int j=0; j<N; ++j) {
val[j] = A[j] & ((1 << (i + 1)) - 1);
}
sort(val, val+N);
int ct = 0;
for (int j=0; j<N; ++j) {
const int cur = A[j] & ((1LL << (i + 1)) - 1);
const int range1 = LB(val, val+N, (1LL << (i + 1)) - cur) - LB(val, val+N, (1 << i) - cur);
const int range2 = LB(val, val+N, (1LL << (i + 2)) - cur) - LB(val, val+N, (1LL << (i + 1)) + (1 << i) - cur);
ct += range1 + range2 + ((A[j] >> (i-1)) & 1);
}
ans |= (ct & 2) << (i-1);
}
cout << ans << '\n';
}
/*
4
3 9 6 6
00110 1 1
01100 1 2
01001 1 3
01001 1 4
10010 2 2
01111 2 3
01111 2 4
01100 3 3
01100 3 4
01100 4 4
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
146 ms |
66028 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1340 ms |
73856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1340 ms |
73856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
146 ms |
66028 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
146 ms |
66028 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |