oj.uz

Submission #389330

# Submission time Handle Problem Language Result Execution time Memory
389330 2021-04-14T03:05:16 Z 8e7 XOR Sum (info1cup17_xorsum) C++14
7 / 100
 1600 ms 4184 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 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;
	int nums = 0;
	for (int i = 0;i < n;i++) {
		int ind = upper_bound(tmp, tmp + n, tmp[i]) - tmp;
		int siz = ind - i;
		ret ^= ((siz / 2) & 1) ? tmp[i] + tmp[i] : 0;
		if ((ind - i) & 1) {
			a[nums++] = tmp[i];
		}
		i = ind - 1;
	}

	n = nums;
	for (int i = 0;i < nums;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;
		for (int j:buck[1][0]) b[ind++] = a[j] & ((1<<(bit + 1)) - 1);
		for (int j:buck[1][1]) b[ind++] = a[j] & ((1<<(bit + 1)) - 1);

		//for (int i = 0;i < n;i++) cout << b[i] << "  ";
		//cout << endl;

		int lef = n - 1, rig = n - 1, ans = 0; //(lef, rig]
		ll tot = 0;
		for (int i = 0;i < n;i++) {
			while (lef > i && b[i] + b[lef] >= (1<<bit)) {
				lef--;
			}
			while (rig > i && b[i] + b[rig] >= (1<<(bit + 1))) {
				rig--;
			}
			lef = max(lef, i), rig = max(rig, i);
			tot += rig - lef;
			ans ^= (rig - lef) & 1;
			if ((b[i] + b[i]) & (1<<bit)) ans ^= 1, tot++;
		}
		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 >> n;
	for (int i = 0;i < n;i++) cin >> tmp[i];
	cout << brute(n) << "\n";
	/*
	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
 */

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1695 ms 4184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1695 ms 4184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Execution timed out 1695 ms 616 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Execution timed out 1695 ms 4184 KB Time limit exceeded
4 Halted 0 ms 0 KB -