oj.uz

Submission #389365

# Submission time Handle Problem Language Result Execution time Memory
389365 2021-04-14T03:38:15 Z 8e7 XOR Sum (info1cup17_xorsum) C++14
100 / 100
 990 ms 28344 KB 
//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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 464 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 27996 KB Output is correct
2 Correct 534 ms 26536 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 27996 KB Output is correct
2 Correct 534 ms 26536 KB Output is correct
3 Correct 695 ms 28252 KB Output is correct
4 Correct 661 ms 27448 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 464 KB Output is correct
3 Correct 83 ms 3380 KB Output is correct
4 Correct 84 ms 3396 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 464 KB Output is correct
3 Correct 565 ms 27996 KB Output is correct
4 Correct 534 ms 26536 KB Output is correct
5 Correct 695 ms 28252 KB Output is correct
6 Correct 661 ms 27448 KB Output is correct
7 Correct 83 ms 3380 KB Output is correct
8 Correct 84 ms 3396 KB Output is correct
9 Correct 967 ms 28248 KB Output is correct
10 Correct 990 ms 28196 KB Output is correct
11 Correct 986 ms 28344 KB Output is correct