Submission #1158200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158200		yonatanl	XOR Sum (info1cup17_xorsum)	C++20	56 / 100	1692 ms	12380 KiB

xorsum

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

#define rep(i, s, e) for (ll i = s; i < e; i++)

using namespace std;
using ll = int;
using vll = vector<ll>;
using vb = vector<bool>;

void solve() {
	ll n;
	cin >> n;
	vll arr(n);
	for (ll i = 0; i < n; i++) cin >> arr[i];
	ll ans = 0;
	for (ll b = 0; b < 29; b++) {
		// Look at the first b bits
		vll cur0; // Keep all the numbers that have 0 in the b bit with only their first b-1 bits
		vll cur1; // Keep all the numbers that have 1 in the b bit with only their first b-1 bits
		ll A = (1LL << (b)) - 1;
		for (ll i = 0; i < n; i++) {
			if ((arr[i] >> b) & (ll)1) cur1.push_back(arr[i] & A);
			else cur0.push_back(arr[i] & A);
		}
		sort(cur0.begin(), cur0.end());
		sort(cur1.begin(), cur1.end());
		long long res = 0;
		ll carry = (ll)1 << b;
		ll pos = 0;
		for (ll j = cur0.size() - 1; j >= 0; j--) {
			for (; pos < cur1.size(); pos++) {
				if (cur0[j] + cur1[pos] >= carry) { break; }
			}
			res += pos;
		}
		ll t = 0;
		pos = cur0.size() - 1;
		for (ll j = 0; j < cur0.size(); j++) {
			for (; pos >= 0; pos--) {
				if (cur0[j] + cur0[pos] < carry) { break; }
			}
			t += cur0.size() - pos - 1;
		}
		pos = cur1.size() - 1;
		for (ll j = 0; j < cur1.size(); j++) {
			for (; pos >= 0; pos--) {
				if (cur1[j] + cur1[pos] < carry) { break; }
			}
			t += cur1.size() - pos - 1;
		}
		for (ll i = 0; i < n; i++) {
			if (((2 * arr[i]) >> b) & 1) { t++; }
		}
		res += t / 2;
		ans += (res % 2) * carry;
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	solve();
}

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