#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=4e5+5,mod=1e9+7,Mx=35e6+7;
int t,tree[2][Mx+7],a[N],n,k,i,j,cnt,ans,s[N],c[N];
void update(int ind,int val,int t){
for(ind;ind<=Mx;ind+=ind&(-ind))
tree[t][ind]+=val;
}
int getans(int ind,int t){
int pas=0;
for(ind;ind>=1;ind-=ind&(-ind))
pas+=tree[t][ind];
return pas;
}
main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(k=1;k<=n;k++){
cin>>a[k];
}
for(k=1;k<=n;k++){
s[k] = a[k]&1;
cnt += c[s[k]^1];
cnt%=2;
c[s[k]]++;
c[s[k]]%=2;
}
if(cnt%2) ans=1;
for(i=1;i<25;i++){
cnt = 0;
for(k=1;k<=n;k++){
//
int c = (a[k]&(1<<i)) > 0;
cnt+=getans((1<<(i+1))-s[k],c)%2; if(cnt>=2) cnt-=2;
if(((1<<i)-s[k])>0) cnt=(cnt-getans(((1<<i)-s[k]),c)%2+2)%2;
if(((1<<i)-s[k])>0) cnt=(cnt+getans(((1<<i)-s[k]),1^c)%2)%2;
update(s[k]+1,1,c);
} //cout<<endl;
for(k=1;k<=n;k++){
int c = (a[k]&(1<<i)) > 0;
update(s[k]+1,-1,c);
s[k]+=a[k]&(1<<i);
}
if(cnt==1) ans+=1<<i;
}
cout<<ans;
}
Compilation message
xorsum.cpp: In function 'void update(int, int, int)':
xorsum.cpp:8:6: warning: statement has no effect [-Wunused-value]
8 | for(ind;ind<=Mx;ind+=ind&(-ind))
| ^~~
xorsum.cpp: In function 'int getans(int, int)':
xorsum.cpp:13:6: warning: statement has no effect [-Wunused-value]
13 | for(ind;ind>=1;ind-=ind&(-ind))
| ^~~
xorsum.cpp: At global scope:
xorsum.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
17 | main(){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
85 ms |
69100 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1685 ms |
10860 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1685 ms |
10860 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
85 ms |
69100 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
85 ms |
69100 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |