Submission #1144435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144435		Agageldi	XOR Sum (info1cup17_xorsum)	C++20	56 / 100	1695 ms	26408 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 6000005
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(s) (int)s.size()

ll T, n, a[N], ans = 0;
map <ll,ll> vis, vip;
vector <ll> v1, v0;

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n; i++){
		cin >> a[i];
	}
	sort(a+1,a+n+1);
	for(ll i = 0;i <= 30; i++) {
		v1.clear();
		v0.clear();
		for(int j = 1; j <= n; j++) {
			if((a[j] & (1LL << i)))v1.pb(a[j] % (1LL << i));
			else v0.pb(a[j] % (1LL << i));
		}
		sort(v1.begin(),v1.end());
		sort(v0.begin(),v0.end());
		int cnt = 0;
		for(int j = 0; j < sz(v1); j++) {
			int l = 0, r = sz(v0) - 1,jog = 0;
			while(l <= r) {
				int md = (l + r) / 2;
				if(v0[md] + v1[j] < (1LL << i)) {
					l = md + 1;
					jog = md + 1;
					continue;
				}
				r = md - 1;
			}
			cnt += jog;
		}
		for(int j = 0; j < sz(v0); j++) {
			int l = j,r = sz(v0) - 1, jog = sz(v0) + 1;
			while(l <= r) {
				int md = (l+r)/2;
				if(v0[md] + v0[j] >= (1LL << i)) {
					r = md - 1;
					jog = md + 1;
					continue;
				}
				l = md + 1;
			}
			cnt += (sz(v0) - jog + 1);
		}
		for(int j = 0; j < sz(v1); j++) {
			int l = j,r = sz(v1) - 1, jog = sz(v1) + 1;
			while(l <= r) {
				int md = (l+r)/2;
				if(v1[md] + v1[j] >= (1LL << i)) {
					r = md - 1;
					jog = md + 1;
					continue;
				}
				l = md + 1;
			}
			cnt += (sz(v1) - jog + 1);
		}
		if(cnt % 2) ans |= (1LL << i);
	}
	cout << ans << '\n';
}

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