#include <bits/stdc++.h>
using namespace std;
#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int N = 1e6 + 25, LGN = 22;
struct trie {
struct node {
int l, r, cnt;
} arr[N * LGN];
int t = 2;
inline int cnt(int p) { return p ? arr[p].cnt : 0; }
int insert(int v, int n, int id, int c) {
if(!id)
id = t++;
//cout << "inserting " << n << ' ' << id << '\n';
if(n == -1) {
arr[id].cnt += c;
return id;
}
if(v >> n & 1)
arr[id].r = insert(v, n - 1, arr[id].r, c);
else
arr[id].l = insert(v, n - 1, arr[id].l, c);
arr[id].cnt = cnt(arr[id].l) + cnt(arr[id].r);
return id;
}
int que(int v, int n, int tar, int id) {
if(!id)
return 0;
//cout << "owo " << tar << ' ' << id << '\n';
if(v >> tar & 1) {
if(n == -1)
return arr[id].cnt;
if(v >> n & 1) {
return que(v, n - 1, tar, arr[id].l);
}
else {
return cnt(arr[id].l) + que(v | (1 << n), n - 1, tar, arr[id].r);
}
}
else {
if(n == -1)
return 0;
if(v >> n & 1) {
return que(v, n - 1, tar, arr[id].l) + cnt(arr[id].r);
}
else {
return que(v | (1 << n), n - 1, tar, arr[id].r);
}
}
}
inline int query(int v, int tar) {
//cout << "here " << v << ' ' << tar << ' ' << arr[1].l << '\n';
return que(v, tar - 1, tar, arr[1].l) + que(v ^ (1 << tar), tar - 1, tar, arr[1].r);
}
} tri[LGN];
signed main() {
int n;
cin >> n;
map<int, int> num;
for(int i = 0, x; i < n; i++) {
cin >> x;
num[x]++;
}
int ans = 0;
for(const auto &[v, cnt] : num) {
if(cnt & 1) {
///*
for(int i = 0; i < LGN; i++) {
int w = tri[i].query(v, i);
//cout << v << ' ' << i << ' ' << w << '\n';
if(w & 1)
ans ^= 1 << i;
}
//*/
}
for(int i = 0; i < LGN; i++)
tri[i].insert(v, i, 1, cnt);
if(1LL * cnt * (cnt + 1) / 2 % 2)
ans ^= v + v;
}
cout << ans << '\n';
}
Compilation message
/tmp/ccxDI92B.o: In function `main':
xorsum.cpp:(.text.startup+0x5): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
xorsum.cpp:(.text.startup+0x9e): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
xorsum.cpp:(.text.startup+0x18d5): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/tmp/ccxDI92B.o: In function `_GLOBAL__sub_I_tri':
xorsum.cpp:(.text.startup+0x5e97): relocation truncated to fit: R_X86_64_PC32 against `.bss'
xorsum.cpp:(.text.startup+0x5eb1): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(vterminate.o): In function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1a): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x27): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
