This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int L = 29;
vector<int> p = {1};
vector<int> merge(vector<int> a, int pw) {
vector<int> b, c;
int n = a.size();
int id = n;
for(int i = 0; i < n; i++) {
if (a[i] >= p[pw+1]) {
id = i;
break;
}
}
for(int i = id; i < n; i++) {
a[i] -= p[pw+1];
b.push_back(a[i]);
}
for(int i = id; i < n; i++) {
a.pop_back();
}
// sudedame du surikiuotus masyvus i viena, islaikydami nemazejancia tvarka
int id1 = 0, id2 = 0;
n = a.size();
int m = b.size();
while(id1 < n && id2 < m) {
// visada galime deti mazesni elementa nesugadindami tvarkos
if (a[id1] < b[id2]) {
c.push_back(a[id1++]);
} else {
c.push_back(b[id2++]);
}
}
// jei dar liko elementu is a
while(id1 < n) {
c.push_back(a[id1++]);
}
// jei dar liko elementu is b
while(id2 < m) {
c.push_back(b[id2++]);
}
return c;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
for(int i = 1; i <= L+1; i++) {
p.push_back(p[i-1]*2);
}
vector<int> cnt(L+1, 0);
vector<int> x(n);
for(int j = L; j >= 0; j--) {
if (j == L) {
for(int i = 0; i < n; i++) {
x[i] = (a[i] % p[j+1]);
}
sort(x.begin(), x.end());
} else {
x = merge(x, j);
}
int pos1 = n, pos2 = n, pos3 = n;
for(int i = 0; i < n; i++) {
pos1 = max(pos1, i+1);
pos2 = max(pos2, i+1);
pos3 = max(pos3, i+1);
while(pos1 >= i+1 && 1*p[j]-x[i] <= x[pos1-1]) pos1--;
while(pos2 >= i+1 && 2*p[j]-x[i] <= x[pos2-1]) pos2--;
while(pos3 >= i+1 && 3*p[j]-x[i] <= x[pos3-1]) pos3--;
int curr = (pos2 - pos1) + (n - pos3);
cnt[j] += curr;
}
}
ll ans = 0;
for(int i = 0; i <= L; i++) {
// cout << cnt[i] << " ";
if (cnt[i] % 2) {
ans += p[i];
}
}
cout << ans << "\n";
return 0;
}
# | 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... |