# include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long le,ri,mid,lee,rii;
long long a[N],b[N],c[N],mp[35],ans,n,answ;
int go1(int le, int ri, int val,int val1) {
ans=-1;
while (le<=ri) {
mid=(le+ri)/2;
if (val+c[mid]>=val1) {
ans=mid;
ri=mid-1;
}
else le=mid+1;
}
return ans;
}
int go2(int le, int ri, int val, int val1) {
ans=-1;
while (le<=ri) {
mid=(le+ri)/2;
if (val+c[mid]<val1) {
ans=mid;
le=mid+1;
}
else ri=mid-1;
}
return ans;
}
int main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
for (int i=0; i<=30; i++) {
for (int j=1; j<=n; j++) {
b[j]+=a[j]&(1LL<<i);
c[j]=b[j];
}
sort(c+1, c+n+1);
for (int j=1; j<=n; j++) {
le=j+1;
ri=n;
lee=go1(j+1,n,c[j],(1LL<<i));
le=j+1;
ri=n;
rii=go2(j+1, n, c[j], (1LL<<(i+1)));
if (rii!=-1 && lee!=-1)
mp[i]+=rii-lee+1;
lee=go1(j+1, n, c[j], (1LL<<(i+1))+(1LL<<i));
rii=n;
if (rii!=-1 && lee!=-1)
mp[i]+=rii-lee+1;
}
}
for (int i=0; i<=30; i++) {
// cout<<mp[i]<<" ";
if (mp[i]%2) answ+=(1LL<<i);
}
for (int i=1; i<=n; i++) {
answ^=(2*a[i]);
}
cout<<answ<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
492 KB |
Output is correct |
2 |
Correct |
18 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1692 ms |
23916 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1692 ms |
23916 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
492 KB |
Output is correct |
2 |
Correct |
18 ms |
492 KB |
Output is correct |
3 |
Correct |
582 ms |
2772 KB |
Output is correct |
4 |
Correct |
577 ms |
2924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
492 KB |
Output is correct |
2 |
Correct |
18 ms |
492 KB |
Output is correct |
3 |
Execution timed out |
1692 ms |
23916 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |