# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
497750 | Ziel | XOR Sum (info1cup17_xorsum) | C++17 | 1396 ms | 131076 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* LES GREATEABLES BRO TEAM
**/
#pragma GCC optimization("g", on)
#pragma GCC optimize ("inline")
#pragma GCC optimization("03")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");
#define int ll
void solve() {
int n;
cin >> n;
vector<int> a(n);
int mx = 0, res = 0;
for (int &x: a) {
cin >> x;
mx = max(mx, x);
}
if (n * n <= 1e8) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
res ^= (a[i] + a[j]);
}
}
} else if (mx * mx <= 4e8) {
set<pair<int, int>> s;
ordered_set<int> occ[mx + 1];
for (int i = 0; i < n; i++) {
s.insert({i, a[i]});
occ[a[i]].insert(i);
}
vector<int> v(mx + mx + 2);
for (int a = 1; a <= mx; a++) {
for (int b = 1; b <= mx; b++) {
for (int pos: occ[a]) {
int k = sz(occ[b]) - occ[b].order_of_key(pos);
v[a + b] += k;
}
}
}
for (int i = 1; i <= mx + mx; i++)
res ^= (v[i] % 2) * i;
}
cout << res;
}
signed main() {
setIO();
int tt = 1;
if (FLAG) {
cin >> tt;
}
while (tt--) {
solve();
}
return 0;
}
void setIO(const string &f) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen((f + ".in").c_str(), "r")) {
freopen((f + ".in").c_str(), "r", stdin);
freopen((f + ".out").c_str(), "w", stdout);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |