# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
67710 | tatatan | XOR Sum (info1cup17_xorsum) | C++11 | 1444 ms | 48632 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.
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int MAXN=1000005;
int n,a[MAXN],b[MAXN],ans;
pii v[MAXN],c[MAXN],d[MAXN];
int main() {
scanf("%d",&n);
for(int i=0;i<n;++i) {
scanf("%d",&a[i]);
v[i]=mp(0,i);
}
for(int i=0;i<30;++i) {
int t1,t2,t3,ci=0,di=0;
LL cnt=0;
for(int j=0;j<n;++j)
if((1<<i)&(a[v[j].nd]))
d[di++]=mp(v[j].st+(1<<i),v[j].nd);
else c[ci++]=v[j];
for(int j=0;j<ci;++j)
v[j]=c[j];
for(int j=0;j<di;++j)
v[j+ci]=d[j];
for(int j=0;j<n;++j)
b[j]=v[j].st;
t1=t2=t3=n;
for(int j=0;j<n;++j) {
while(t1&&b[t1-1]>=(1<<i)-b[j])
--t1;
while(t2&&b[t2-1]>=(1<<(i+1))-b[j])
--t2;
while(t3&&b[t3-1]>=(1<<(i+1))+(1<<i)-b[j])
--t3;
cnt+=(n-t1-(t3-t2));
}
for(int j=0;j<n;++j)
if((b[j]*2)&(1<<i)) --cnt;
cnt/=2;
for(int j=0;j<n;++j)
if((b[j]*2)&(1<<i)) ++cnt;
if(cnt&1) ans+=(1<<i);
}
printf("%d\n",ans);
}
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... |