#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;
typedef pair<int,int> pii;
const int MAX_N = 1000000;
const int MAX_LOGV = 31;
int arr[MAX_N];
int remain[MAX_N];
ll digitNum[MAX_LOGV];
int binarySearch(int i,int digit,int lo,int hi,int loFlag,int hiFlag){
assert(loFlag!=hiFlag and lo<hi);
while(lo+1<hi){
int mid = (lo+hi)/2;
if((((remain[i]+remain[mid])&(1<<digit))==0)==loFlag){
lo = mid;
}else{
hi = mid;
}
}
return hi;
}
int searchLo(int i,int digit,int N,bool loFlag){
int lo = i;
while(lo<N and loFlag==(((remain[i]+remain[lo])&(1<<digit))==0)) lo++;
return lo;
}
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 loFlag = ((remain[0]*2)&(1<<digit))==0;
bool hiFlag = ((remain[0]+remain[N-1])&(1<<digit))==0;
if(loFlag!=hiFlag){
lo = binarySearch(0,digit,0,N-1,loFlag,hiFlag);
hi = N;
}else{
lo = searchLo(0,digit,N,loFlag);
hi = lo==N ? N : binarySearch(0,digit,lo,N-1,!loFlag,hiFlag);
}
digitNum[digit]+= loFlag ? hi-lo : N-(hi-lo);
//cout<<(loFlag ? 1 : 0)<<" , "<<lo<<" , "<<hi<<" , "<<(loFlag ? hi-lo : N-(hi-lo))<<'\n';
for(int i=1;i<N;i++){
//cout<<remain[i]*2<<" , "<<(1<<digit)<<" , "<<((remain[i]*2)&(1<<digit))<<'\n';
bool newLoFlag = ((remain[i]*2)&(1<<digit))==0;
hiFlag = ((remain[i]+remain[N-1])&(1<<digit))==0;
if(loFlag==newLoFlag){
if(newLoFlag==hiFlag){
//lo = lo==N ? searchLo(i,digit,N,newLoFlag) : binarySearch(i,digit,i,lo,newLoFlag,!newLoFlag);
lo = searchLo(i,digit,N,newLoFlag);
hi = lo==N ? N : binarySearch(i,digit,lo,N-1,!newLoFlag,hiFlag);
}else{
assert(hi==N);
lo = binarySearch(i,digit,i,N-1,newLoFlag,hiFlag);
}
}else{
if(newLoFlag==hiFlag){
lo = lo==N ? searchLo(i,digit,N,newLoFlag) : binarySearch(i,digit,i,hi,newLoFlag,!newLoFlag);
hi = lo==N ? N : binarySearch(i,digit,lo,N-1,!newLoFlag,hiFlag);
}else{
lo = binarySearch(i,digit,i,N-1,newLoFlag,hiFlag);
hi = N;
}
}
digitNum[digit]+= newLoFlag ? hi-lo : N-i-(hi-lo);
//cout<<(loFlag ? 1 : 0)<<" , "<<(newLoFlag ? 1 : 0)<<" , "<<lo<<" , "<<hi<<" , "<<(newLoFlag ? hi-lo : N-i-(hi-lo))<<'\n';
loFlag = newLoFlag;
}
}
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 |
60 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1689 ms |
9044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1689 ms |
9044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
