oj.uz

답안 #389325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389325 2021-04-14T03:00:41 Z 8e7 XOR Sum (info1cup17_xorsum) C++14
0 / 100
 147 ms 4212 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#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 main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) cin >> tmp[i];
	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;
			//cout << lef << " " << rig << endl;
			ans ^= (rig - lef) & 1;
			if ((b[i] + b[i]) & (1<<bit)) ans ^= 1, tot++;
		}

		//cout << tot << endl;
		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();
	}
	cout << ret << endl;
}
/*
4
3 9 6 6
 */

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 4212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 4212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -