| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1158214 | yonatanl | XOR Sum (info1cup17_xorsum) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define rep(i, s, e) for (ll i = s; i < e; i++)
using namespace std;
using ll = int;
using vll = vector<ll>;
using vb = vector<bool>;
void solve() {
ll n;
cin >> n;
ll arr[ll(1e6) + 1];
for (ll i = 0; i < n; i++) cin >> arr[i];
ll ans = 0;
for (ll b = 0; b < 30; b++) {
// Look at the first b bits
vll cur0; // Keep all the numbers that have 0 in the b bit with only their first b-1 bits
vll cur1; // Keep all the numbers that have 1 in the b bit with only their first b-1 bits
ll A = (1LL << (b)) - 1;
ll res = 0;
for (ll i = 0; i < n; i++) {
if ((arr[i] >> b) & (ll)1) cur1.push_back(arr[i] & A);
else cur0.push_back(arr[i] & A);
}
sort(cur0.begin(), cur0.end());
sort(cur1.begin(), cur1.end());
ll carry = (ll)1 << b;
ll pos = 0;
pos = cur0.size() - 1;
for (ll j = 0; j < cur0.size(); j++) {
for (; pos >= 0; pos--) {
if (cur0[j] + cur0[pos] < carry) { break; }
}
res += cur0.size() - pos - 1;
}
pos = cur1.size() - 1;
for (ll j = 0; j < cur1.size(); j++) {
for (; pos >= 0; pos--) {
if (cur1[j] + cur1[pos] < carry) { break; }
}
res += cur1.size() - pos - 1;
}
res /= 2;
ans += (res % 2) * carry;
}
cout << ans << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}