Submission #1316216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316216		Petrix	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	810 ms	24092 KiB

xorsum

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define int long long
vector<int> v,v1,v2;

int solve(int a){
	int aux=v.size(),rasp=0,i;
	for(i=0;i<v.size();i++){
		aux=max(aux,i);
		while(aux>i && v[i]+v[aux-1]>=a) aux--;
		rasp^=(aux-i)%2;
	}
	return rasp;
}

signed main()
{
	int n,rasp=0,a,i,cnt1,cnt2,cnt;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a;
		v.push_back(a);
	}
	sort(v.begin(),v.end());
	for(i=(1<<29);i;i/=2){
        v1.clear();v2.clear();
		for(int j:v){
			if(j<2*i) v1.push_back(j);
			else v2.push_back(j-2*i);
		}
		v.clear();
        cnt1=cnt2=0;
        while(cnt1<v1.size() && cnt2<v2.size()){
            if(v1[cnt1]<=v2[cnt2]){
                v.push_back(v1[cnt1]);cnt1++;
            }else{
                v.push_back(v2[cnt2]);cnt2++;
            }
        }
        while(cnt1<v1.size()){
            v.push_back(v1[cnt1]);cnt1++;
        }
        while(cnt2<v2.size()){
            v.push_back(v2[cnt2]);cnt2++;
        }
		cnt=(solve(4*i)^solve(3*i)^solve(2*i)^solve(i));
		rasp+=i*cnt;
	}
	cout<<rasp;
}

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