제출 #389365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389365		8e7	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	990 ms	28344 KiB

xorsum

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <random>
#define ll long long
#define maxn 1000005
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define pii pair<int, int>
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<lcass T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
vector<int> buck[2][2];
int a[maxn], b[maxn], tmp[maxn];
int type = 1;
int solve(int n) {
	buck[0][0].clear(), buck[0][1].clear(), buck[1][0].clear(), buck[1][1].clear();

	sort(tmp, tmp + n);
	int ret = 0;
	for (int i = 0;i < n;i++) {
		a[i] = tmp[i];
	}
	for (int i = 0;i < n;i++) buck[0][0].push_back(i);

	for (int bit = 0;bit < 30;bit++) {
		for (int i = 0;i < 2;i++) {
			for (int j:buck[0][i]) {
				buck[1][(a[j] & (1<<bit)) ? 1 : 0].push_back(j);
			}
		}

		int ind = 0, mid;
		for (int j:buck[1][0]) b[ind++] = a[j] & ((1<<(bit + 1)) - 1);
		mid = ind;
		for (int j:buck[1][1]) b[ind++] = a[j] & ((1<<(bit + 1)) - 1);

		if (type == 0) {
			for (int i = 0;i < n;i++) cout << b[i] << "  ";
			cout << endl;
		}

		int pnt, ans = 0; //(lef, rig]
		ll tot = 0;

		pnt = mid - 1;
		for (int i = 0;i < mid;i++) {
			while (pnt >= i && b[pnt] + b[i] >= (1<<bit)) pnt--;
			pnt = max(pnt, i - 1);
			//cout << i << " " << mid - 1 - pnt << endl;
			tot += mid - 1 - pnt;
			ans ^= (mid - 1 - pnt) & 1;
		}

		pnt = n - 1;
		for (int i = mid;i < n;i++) {
			while (pnt >= i && ((b[pnt] + b[i]) & (1<<bit))) pnt--;
			pnt = max(pnt, i - 1);
			//cout << " " << i << " " << n - 1 - pnt << endl;
			tot += n - 1 - pnt;
			ans ^= (n - 1 - pnt) & 1;
		}

		pnt = mid;

		for (int i = mid - 1;i >= 0;i--) {
			while (pnt < n && ((b[i] + b[pnt]) & (1<<bit))) pnt++;
			//cout << i << " " << pnt - mid << endl;
			tot += pnt - mid;
			ans ^= (pnt - mid) & 1;
		}

		if (type == 0) cout << tot << "\n";
		ret ^= (1<<bit) * ans;
		buck[0][0].clear(), buck[0][1].clear();
		buck[0][0] = buck[1][0], buck[0][1] = buck[1][1];
		buck[1][0].clear(), buck[1][1].clear();
	}
	return ret;
}
int brute(int n) {
	int ret = 0;
	for (int i = 0;i < n;i++) {
		for (int j = i;j < n;j++) {
			ret ^= (tmp[i] + tmp[j]);
		}
	}
	return ret;
}
int main() {
	io
	int n;

	//cin >> type;
	if (type == 1) {
		cin >> n;
		for (int i = 0;i < n;i++) cin >> tmp[i];
		cout << solve(n) << "\n";
	} else {
		while (true) {
			n = rand() % 5 + 1;
			for (int i = 0;i < n;i++) tmp[i] = rand() % 8;
			if (brute(n) != solve(n)) {
				cout << n << endl;
				for (int i = 0;i < n;i++) cout << tmp[i] << " ";
				cout << endl;
				cout << brute(n) << " " << solve(n) << endl;
				return 0;
			}
		}
	}


}
/*
4
3 9 6 6

1
3
2 3 7

1
5
0 3 5 5 6
 */

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