| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 389571 | rk42745417 | XOR Sum (info1cup17_xorsum) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}