Submission #1144443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144443		Agageldi	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	598 ms	26272 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 n, ans;
vector <ll> v1, v0, a;

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n; i++){
		ll x;
		cin >> x;
		a.pb(x);	
	}
	for(ll i = 0; i <= 29; i++) {
		v1.clear();
		v0.clear();
		for(int j = 0; j < n; j++) {
			if((a[j] & (1LL << i)))v1.pb(a[j]);
			else v0.pb(a[j]);
		}
		a.clear();
		for(auto j : v0) a.pb(j);
		for(auto j : v1) a.pb(j);
		for(int j = 0; j< sz(v0);j++) {
			v0[j] %= (1LL<<i);
		}
		for(int j = 0; j< sz(v1);j++) {
			v1[j] %= (1LL<<i);
		}
		int cnt = 0, jog = sz(v1);
		for(int j = 0; j < sz(v0); j++) {
			while(jog > 0 && (v1[jog-1] + v0[j]) >= (1LL << i)) jog--;
			cnt += jog;
		}
		jog = sz(v1);
		int ans1 = 0, ans2 = 0;
		for(int j = 0; j < sz(v1);j++) {
			while(jog > 0 && (v1[jog - 1] + v1[j]) >= (1LL << i)) jog--;
			ans1 += (sz(v1) - jog);
			ans1 += ((v1[j]*2) >= (1LL<<i));
		}
		ans1/=2;
		jog = sz(v0);
		for(int j = 0; j < sz(v0);j++) {
			while(jog > 0 && (v0[jog - 1] + v0[j]) >= (1LL << i)) jog--;
			ans2 += (sz(v0) - jog);
			ans2 += ((v0[j] * 2) >= (1LL<<i));
		}
		ans2/=2;
		cnt += (ans1 + ans2);
		if(cnt % 2) ans |= (1LL << i);
	}
	cout << ans << '\n';
}

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