#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
struct node{
lld 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);
}*/
lld 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;
}
lld 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];
int M=50;
node *trie[M];
lld pow[M];
pow[0]=1;
for(int i=1;i<M;i++)pow[i]=pow[i-1]*2;
for(int i=0;i<M;i++)trie[i]=new node();
lld ans1=0;
lld answer[M];
for(int i=0;i<M;i++)answer[i]=0;
for(int i=0;i<n;i++){
for(int j=0;j<M;j++){
insert(trie[j],arr[i],pow[j]);
lld 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);
}
answer[j]%=2;
}
//for(int j=i;j<n;j++)ans1^=(arr[i]+arr[j]);
}
//cout<<ans1<<endl;
lld ans=0;
for(int i=0;i<M;i++){
if(answer[i]!=0){
ans+=pow[i];
}
}
cout<<ans<<endl;
return 0;
}
Compilation message
xorsum.cpp: In function 'int main()':
xorsum.cpp:88:6: warning: unused variable 'ans1' [-Wunused-variable]
lld ans1=0;
^~~~
xorsum.cpp: In function 'lld count(node*, lld, lld, int)':
xorsum.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
428 ms |
128552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1654 ms |
18240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1654 ms |
18240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
428 ms |
128552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
428 ms |
128552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
