Submission #410484

#	Time	Username	Problem	Language	Result	Execution time	Memory
410484		nichke	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	826 ms	57828 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
 
int n, res;
int ar[1000006];
int tar[1000006];

vector< pair<int, int> > tmp, cur;
 
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
		tmp.push_back({ar[i], 0});
	}
	for (int j = 0; j < 31; j++) {
		for (auto i : tmp) {
			if (i.first & (1 << j)) continue;
			cur.push_back(i);
		}
		for (auto i : tmp) {
			if (i.first & (1 << j)) {
				cur.push_back({i.first, i.second + (1 << j)});
			}
		}
		int p1, p2, p3, sum = 0;
		p1 = n - 1, p2 = n - 1, p3 = n - 1;
		for (int i = 0; i < n; i++) {
			p1 = max(p1, i - 1);
			p2 = max(p2, i - 1);
			p3 = max(p3, i - 1);
			while (p1 >= i && cur[i].second + cur[p1].second >= (1 << j)) p1--;
			while (p2 >= i && cur[i].second + cur[p2].second >= 2 * (1 << j)) p2--;
			while (p3 >= i && cur[i].second + cur[p3].second >= 3 * (1 << j)) p3--;
			sum += p2 - p1 + n - 1 - p3;
		}
		if (sum & 1) {
			res += (1 << j);
		}
		swap(tmp, cur);
		cur.clear();
	}
	cout << res << '\n';
	return 0;
}

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