#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
struct node{
int sub;
node *l,*r;
};
void init(node *n){
n=new node();
n->sub=0;
}
void extend(node *n){
if(!n->l){
n->l=new node();
n->r=new node();
n->l->sub=0;
n->r->sub=0;
}
}
void insert(node *n,lld num,lld pow){
//cout<<num<<" "<<pow<<endl;
n->sub++;
if(pow==0){
return;
}
extend(n);
//cout<<n->l<<endl;
if((num&pow)>0){//cout<<"R";
insert(n->r,num,pow/2);
}else insert(n->l,num,pow/2);
}
/*bool search(node *n, lld num,lld pow){
if(!n)return false;
if(pow==0){
return n->sub;
}
if((num&pow)>0){
return search(n->r,num,pow/2);
}return search(n->l,num,pow/2);
}*/
int count(node *n, lld num, lld pow,int first){
//cout<<num<<" "<<pow<<" "<<first<<endl;
if(!n)return 0;
if(pow==0){
if(first==0)return 0;
else return n->sub;
}
int bit=(num&pow);
if(bit>0)bit=1;
//if(n->r)cout<<n->r->sub<<endl;
if(first==0){
if(bit){
if(n->r)return count(n->l,num,pow/2,0)+n->r->sub;
}else{
return count(n->r,num,pow/2,0);
}
}else{
if(bit==0){
if(n->l)return count(n->r,num,pow/2,1)+n->l->sub;
}else{
return count(n->l,num,pow/2,1);
}
}
}
//node *test;
int main(){
/*test=new node();
test->sub=0;
insert(test,10,16);
insert(test,14,16);
cout<<count(test,24,16,0);
for(int i=0;i<32;i++){
cout<<count(test,i,16,0)<<" "<<count(test,i,16,1)<<" "<<i<<endl;
}*/
//insert(test,2,1);
//cout<<search(test,1,1);
int n;
cin>>n;
lld arr[n];
for(int i=0;i<n;i++)cin>>arr[i];
node *trie[31];
lld pow[31];
for(int i=1;i<=30;i++)pow[i]=(1<<i);
for(int i=0;i<=30;i++)trie[i]=new node();
lld ans=0;
int answer[31];
for(int i=0;i<31;i++)answer[i]=0;
for(int i=0;i<n;i++){
for(int j=0;j<=30;j++){
insert(trie[j],arr[i],pow[j]);
int bit=(arr[i]&pow[j]);
if(bit){
answer[j]+=count(trie[j]->l,arr[i],pow[j]/2,1);
answer[j]+=count(trie[j]->r,arr[i],pow[j]/2,0);
}else{
answer[j]+=count(trie[j]->l,arr[i],pow[j]/2,0);
answer[j]+=count(trie[j]->r,arr[i],pow[j]/2,1);
}
}
//for(int j=i;j<n;j++)ans^=(arr[i]+arr[j]);
}
for(int i=0;i<31;i++){
if(answer[i]%2!=0){
ans+=pow[i];
}
}
cout<<ans<<endl;
return 0;
}
Compilation message
xorsum.cpp: In function 'int count(node*, lld, lld, int)':
xorsum.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
251 ms |
48536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1634 ms |
14128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1634 ms |
14128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
251 ms |
48536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
251 ms |
48536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
