Submission #229278

#	Time	Username	Problem	Language	Result	Execution time	Memory
229278		acm	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	31 ms	3960 KiB

xorsum

#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 410000;

int n, a[N], tmp[N], sum[N];

template <class T>
inline void read(T &x) {
	x = 0;
	char ch = getchar(), w = 0;
	while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	x = w ? -x : x;
	return;
}

inline void mergeSort(int id) {
	int p = 0, q = 0;
	for (R int i = 1; i <= n; ++i)
		if (a[i] & (1 << id))
			tmp[++q] = a[i];
		else
			a[++p] = a[i];
	for (R int i = 1; i <= q; ++i)
		a[p + i] = tmp[i];
	return;
}

int main() {
	read(n);
	for (R int i = 1; i <= n; ++i) read(a[i]);
	int num = 0, ans = 0;
	for (R int i = 1; i <= n; ++i) {
		if ((a[i] & 1 ? num : i - 1 - num) & 1)
			ans ^= 1;
		num += 1 - (a[i] & 1);
	}
	for (R int i = 1; i <= 24; ++i) {
		mergeSort(i - 1);
		int w = (1 << i) - 1;
		for (R int j = 1; j <= n; ++j)
			sum[j] = sum[j - 1] + ((a[j] >> i) & 1);
		for (R int j = n, tl = 1; j; --j) {
			tl = min(tl, j);
			while (tl < j && (a[j] & w) + (a[tl] & w) < 1 << i)
				++tl;
			if (a[j] & (1 << i)) {
				if ((tl - 1 - sum[tl - 1]) & 1) ans ^= 1 << i;
				if ((sum[j - 1] - sum[tl - 1]) & 1) ans ^= 1 << i;
			}
			else {
				if (sum[tl - 1] & 1) ans ^= 1 << i;
				if ((j - tl - sum[j - 1] + sum[tl - 1]) & 1) ans ^= 1 << i;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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