#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
typedef vector < int > vi;
const int mod = 1e9 + 7;
const int N = 1e6 + 6;
pp one[N],zer[N],O[N],Z[N];
int T[N],A[N],o,z,zz,oo,n,i,j,l,x,ans;
ll t;
int main (){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
if(A[i]&1) one[++o] = mp(0,i);
else zer[++z] = mp(0,i);
}
for(j=0;j<31;j++){
t = 0;
for(i=1;i<=n;i++){
x = A[i];
if(x & (1<<j)){
t += o+1 - (int)(lower_bound(one+1 , one+o+1 , mp((1<<j)-T[i] , -1)) - one);
t += (int)(lower_bound(zer+1 , zer+z+1 , mp((1<<j)-T[i] , -1)) - zer-1);
}
else{
t += z+1 - (int)(lower_bound(zer+1 , zer+z+1 , mp((1<<j)-T[i] , -1)) - zer);
t += (int)(lower_bound(one+1 , one+o+1 , mp((1<<j)-T[i] , -1)) - one-1);
}
}
for(i=1;i<=n;i++)
if((A[i]+A[i]) & (1<<j))
t++;
// if(t&1) assert(0);
t >>= 1;
if(t&1)
ans += 1 << j;
for(i=1;i<=n;i++)
T[i] += A[i] & (1 << j);
////
zz = oo = 0;
for(i=1;i<=z;i++){
l = zer[i].nd;
if(A[l] & (1<<j+1))
O[++oo] = mp(T[l],l);
else
Z[++zz] = mp(T[l],l);
}
for(i=1;i<=o;i++){
l = one[i].nd;
if(A[l] & (1<<j+1))
O[++oo] = mp(T[l],l);
else
Z[++zz] = mp(T[l],l);
}
for(i=1;i<=oo;i++) one[i]=O[i]; o = oo;
for(i=1;i<=zz;i++) zer[i]=Z[i]; z = zz;
}
printf("%d",ans);
return 0;
}
Compilation message
xorsum.cpp: In function 'int main()':
xorsum.cpp:59:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
if(A[l] & (1<<j+1))
~^~
xorsum.cpp:66:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
if(A[l] & (1<<j+1))
~^~
xorsum.cpp:72:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(i=1;i<=oo;i++) one[i]=O[i]; o = oo;
^~~
xorsum.cpp:72:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(i=1;i<=oo;i++) one[i]=O[i]; o = oo;
^
xorsum.cpp:73:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(i=1;i<=zz;i++) zer[i]=Z[i]; z = zz;
^~~
xorsum.cpp:73:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(i=1;i<=zz;i++) zer[i]=Z[i]; z = zz;
^
xorsum.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
xorsum.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&A[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
504 KB |
Output is correct |
| 2 |
Correct |
23 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1674 ms |
27724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1674 ms |
27724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
504 KB |
Output is correct |
| 2 |
Correct |
23 ms |
504 KB |
Output is correct |
| 3 |
Correct |
916 ms |
27724 KB |
Output is correct |
| 4 |
Correct |
926 ms |
27724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
504 KB |
Output is correct |
| 2 |
Correct |
23 ms |
504 KB |
Output is correct |
| 3 |
Execution timed out |
1674 ms |
27724 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
