Submission #97673

#	Time	Username	Problem	Language	Result	Execution time	Memory
97673		KLPP	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	1637 ms	86264 KiB

xorsum

#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];
	int M=40;
	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;
	int 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]);
			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++)ans1^=(arr[i]+arr[j]);
	}
	//cout<<ans1<<endl;
	lld ans=0;
	for(int i=0;i<M;i++){
		if(answer[i]%2!=0){
			ans+=pow[i];
		}
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:88:6: warning: unused variable 'ans1' [-Wunused-variable]
  lld ans1=0;
      ^~~~
xorsum.cpp: In function 'int count(node*, lld, lld, int)':
xorsum.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23