#pragma GCC optimize("O3")
#include <unistd.h>
#include <bits/stdc++.h>
using namespace std;
namespace io {
const signed IS=1<<20, OS=1<<18;
char I[IS*32+1],*J=I,O[OS],*K=O;
inline void daer(){if(J>=I+IS-64){char*p=I;do*p++=*J++;while(J!=I+IS);p[read(0,p,I+IS-p)]=0;J=I;}}
template<int N=10,typename T=int>inline T getu(){daer();T x=0;int k=0;do x=x*10+*J-'0';while(*++J>='0'&&++k<N);++J;return x;}
template<int N=10,typename T=int>inline T geti(){daer();bool e=*J=='-';J+=e;return(e?-1:1)*getu<N,T>();}
inline void flush(){write(1,O,K-O);K=O;}
template<int N=10,typename T=int>inline void putu(T n){char s[(N+7)/8*8],*p=s;int k=0;do*p++=n%10+48;while((n/=10)&&++k<N);do*K++=*--p;while(p!=s);*K++=10;if(K>=O+OS-64)flush();}
template<int N=10,typename T=int>inline void puti(T n){if(n<0)*K++='-',n=-n;putu<N,T>(n);}
struct f{f(){I[read(0,I,IS)]=0;}~f(){flush();}}flu;
};
using namespace io;
typedef long long ll;
const int MAX_N = 1000000;
const int MAX_LOGV = 31;
int arr[MAX_N];
int remain[MAX_N];
ll digitNum[MAX_LOGV];
void run(){
int N = getu<7>();
memset(digitNum,0,sizeof(digitNum));
for(int i=0;i<N;i++){
arr[i] = getu<9>();
}
for(int digit=0;digit<MAX_LOGV;digit++){
for(int i=0;i<N;i++){
remain[i] = arr[i]&((1<<(digit+1))-1);
}
sort(remain,remain+N);
//for(int i=0;i<4;i++)cout<<remain[i]<<" ";
//cout<<'\n';
int lo=0,hi=0;bool flag = ((remain[0]*2)&(1<<digit))==0;
for(int i=0;i<N;i++){
//cout<<remain[i]*2<<" , "<<(1<<digit)<<" , "<<((remain[i]*2)&(1<<digit))<<'\n';
bool newFlag = ((remain[i]*2)&(1<<digit))==0;
//lo=i;
if(flag!=newFlag or i==0){
lo = i;
while(lo<N and (newFlag^(((remain[i]+remain[lo])&(1<<digit))>0))) lo++;
hi = lo;
while(hi<N and (newFlag^(((remain[i]+remain[hi])&(1<<digit))==0))) hi++;
}else{
while(lo>i and (newFlag^(((remain[i]+remain[lo-1])&(1<<digit))==0))) lo--;
while(hi>lo and (newFlag^(((remain[i]+remain[hi-1])&(1<<digit))>0))) hi--;
}
digitNum[digit]+= newFlag ? hi-lo : N-i-(hi-lo);
//cout<<(flag ? 1 : 0)<<" , "<<(newFlag ? 1 : 0)<<" , "<<lo<<" , "<<hi<<" , "<<(newFlag ? hi-lo : N-i-(hi-lo))<<'\n';
flag = newFlag;
}
}
int ret = 0;
for(int digit=0;digit<MAX_LOGV;digit++){
ret+= (digitNum[digit]&1) ? (1<<digit) : 0;
}
putu(ret);
}
int main(){
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
run();
return 0;
}
Compilation message
xorsum.cpp: In function 'void io::flush()':
xorsum.cpp:12:27: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | inline void flush(){write(1,O,K-O);K=O;}
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1697 ms |
9060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1697 ms |
9060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
