제출 #1139817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139817		stdfloat	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	522 ms	17968 KiB

xorsum

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

using ll = long long;

#define sz(v)	(int)(v).size()
#define all(v)	(v).begin(), (v).end()

int big(vector<int>& v, vector<int>& u, int K, bool tr) {
	int ans = 0;
	int r = sz(u) - 1;
	for (int i = 0; i < sz(v); i++) {
		while (0 <= r && v[i] + u[r] >= K) r--;

		ans += sz(u) - max((tr ? i - 1 : INT_MIN), r) - 1;
	}

	return ans;
}

int sml(vector<int>&v, vector<int>&u, int K) {
	return sz(v) * sz(u) - big(v, u, K, false);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;

	vector<int> a(n);
	for (auto &i : a)
		cin >> i;

	int ans = 0;
	for (int k = 0; k < 31; k++) {
		int K = 1 << k;
		vector<int> zr, one;
		for (int i = 0; i < n; i++)
			(a[i] >> k & 1 ? one : zr).push_back(i);

		vector<int> b = zr;
		b.insert(b.end(), all(one));

		for (auto &i : zr)
			i = a[i] % K;
		for (auto &i : one)
			i = a[i] % K;
		for (auto &i : b)
			i = a[i];

		a = b;

		int x = big(zr, zr, K, true), y = big(one, one, K, true), z = sml(zr, one, K);

		if ((x + y + z) & 1) ans ^= K;
	}

	cout << ans;
}

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