#include <bits/stdc++.h>
using namespace std;
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=1e6+6;
#define int64_t int
int n;
int64_t a[N],b[N],tmp[N],tmpB[N],vec0[N],n0,vec1[N],n1,freq[2];
void Sort(int pos){
freq[0]=freq[1]=0;
for(int i=1;i<=n;++i){
freq[(a[i]>>pos)&(int64_t)1]++;
}
freq[1]+=freq[0];
for(int i=n;i>=1;--i){
int id=(a[i]>>pos)&(int64_t)1;
b[freq[id]]=a[i];
tmpB[freq[id]]=tmp[i];
if(id==1){
tmpB[freq[id]]|=1<<pos;
}
freq[id]--;
}
for(int i=1;i<=n;++i){
a[i]=b[i];
tmp[i]=tmpB[i];
}
}
int Check(int pos){
int res=0;
n0=n1=0;
for(int i=1;i<=n;++i){
if((a[i]>>pos)&1){
vec1[n1++]=tmp[i];
}
else{
vec0[n0++]=tmp[i];
}
}
int ptr=n0-1;
int ptr1=n1-1;
int ptr2=n1-1;
for(int i=0;i<max(n0,n1);++i){
if(i<n0){
int64_t val=((int64_t)1<<pos)-vec0[i];
while(ptr>=0&&vec0[ptr]>=val){
ptr--;
}
if(ptr+1<=i){
res^=(i-(ptr+1)+1)&1;
}
int64_t val1=((int64_t)1<<pos)-vec0[i];
while(ptr1>=0&&vec1[ptr1]>=val1){
ptr1--;
}
res^=(ptr1+1)&1;
}
if(i<n1){
int64_t val2=((int64_t)1<<pos)-vec1[i];
while(ptr2>=0&&vec1[ptr2]>=val2){
ptr2--;
}
if(ptr2+1<=i){
res^=(i-(ptr2+1)+1)&1;
}
}
}
Sort(pos);
return res;
}
void Sub2(){
int64_t ans=0;
for(int i=0;i<=30;++i){
if(Check(i)){
ans+=(int64_t)1<<i;
}
}
cout<<ans;
}
inline int ReadInt()
{
char c;
int sign = 1;
for (c = getchar(); c < '0' || c > '9'; c = getchar())
if (c == '-') sign = -sign;
int res = c - '0';
for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
res = res * 10 + c - '0';
return res * sign;
}
int32_t main()
{
// freopen("info1cup17_xorsum.inp","r",stdin);
// freopen("info1cup17_xorsum.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
n=ReadInt();
for(int i=1;i<=n;++i){
a[i]=ReadInt();
}
Sub2();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
512 KB |
Output is correct |
2 |
Correct |
8 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
22880 KB |
Output is correct |
2 |
Correct |
531 ms |
21452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
22880 KB |
Output is correct |
2 |
Correct |
531 ms |
21452 KB |
Output is correct |
3 |
Correct |
679 ms |
23008 KB |
Output is correct |
4 |
Correct |
651 ms |
22008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
512 KB |
Output is correct |
2 |
Correct |
8 ms |
512 KB |
Output is correct |
3 |
Correct |
95 ms |
2680 KB |
Output is correct |
4 |
Correct |
95 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
512 KB |
Output is correct |
2 |
Correct |
8 ms |
512 KB |
Output is correct |
3 |
Correct |
613 ms |
22880 KB |
Output is correct |
4 |
Correct |
531 ms |
21452 KB |
Output is correct |
5 |
Correct |
679 ms |
23008 KB |
Output is correct |
6 |
Correct |
651 ms |
22008 KB |
Output is correct |
7 |
Correct |
95 ms |
2680 KB |
Output is correct |
8 |
Correct |
95 ms |
2680 KB |
Output is correct |
9 |
Correct |
868 ms |
22852 KB |
Output is correct |
10 |
Correct |
874 ms |
22904 KB |
Output is correct |
11 |
Correct |
891 ms |
22840 KB |
Output is correct |