| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 97713 |
2019-02-17T18:53:02 Z |
KLPP |
XOR Sum (info1cup17_xorsum) |
C++14 |
|
1600 ms |
128528 KB |
#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;
int even=0;
for(int i=n-1;i>-1;i--){
if(arr[i]%2==1)answer[0]+=even;
else even++;
answer[0]%=2;
}
for(int i=0;i<n;i++){
for(int j=1;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 'lld 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 |
417 ms |
128528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1642 ms |
18404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1642 ms |
18404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
128528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
128528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
