Submission #1156711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156711		adlin	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	807 ms	34148 KiB

xorsum

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back

using namespace std;

typedef long long ll;

const int maxn = 1000001;

int n,a[maxn],b[maxn];

ll cnt[30];

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	
	vector <pair<int,int>> v;
	
	for(int i = 1; i <= n; i++){
		v.pb({0,i});
	}
	
	for(int bt = 0; bt < 30; bt++){
		vector <pair<int,int>> v1,v2;
		for(int i = 0; i < v.size(); i++){
			if(a[v[i].S] & (1 << bt)){
				v2.pb({v[i].F + (1 << bt),v[i].S});
			}
			else {
				v1.pb({v[i].F,v[i].S});
			}
		}
		v.clear();
		for(auto i : v1) v.pb(i);
		for(auto i : v2) v.pb(i);
		for(int i = 0; i < v.size(); i++) b[i + 1] = v[i].F;
		int u1 = n, u2 = n, u3 = n;
		for(int i = 1; i <= n; i++){
			while(u1 && b[i] + b[u1] >= (1 << bt)) u1--;
			while(u2 && b[i] + b[u2] >= (1 << (bt + 1))) u2--;
			while(u3 && b[i] + b[u3] >= (1 << bt) + (1 << (bt + 1))) u3--;
			cnt[bt] += u2 - u1 + n - u3;
		}
		for(int i = 1; i <= n; i++){
			if((b[i] + b[i]) & (1 << bt)) cnt[bt]++;
		}
		cnt[bt] /= 2;
	}
	
	ll ans = 0;
	
	for(int i = 0; i < 30; i++){
		if(cnt[i] & 1){
			ans += (1 << i);
		}
	}
	
	cout << ans;
	
	return 0;
}

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