oj.uz

Submission #362256

# Submission time Handle Problem Language Result Execution time Memory
362256 2021-02-02T11:16:26 Z SeDunion XOR Sum (info1cup17_xorsum) C++17
100 / 100
 1299 ms 21612 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;
//
// bit
// 2^bit
// a[i] %= 2^(bit+1)
// 1 <= a[i] <= 2^(bit+1)-1
// 2 <= a[i] + a[j] <= 2^(bit+2)-2
// 0010000000
// 0011111111
// 0110000000
// 0111111111
//
// 2^bit <= a[i] + a[j] <= 2^(bit+1)-1
// 2^(bit+1)+2^(bit) <= a[i] + a[j] <= 2^(bit+2)-1

const int LOG = 30;

int a[N], b[N], c[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) cin >> a[i], b[i] = a[i] % (1ll<<LOG);
	int ans = 0;
	for (int bit = LOG-1 ; bit >= 0 ; -- bit) {
		//cout << (1<<bit) << ": ";
		if (b[n] >= (1ll << (bit + 1))) {
			int j = n;
			while (j > 1 && b[j - 1] >= (1ll << (bit + 1))) --j;
			for (int i = j ; i <= n ; ++ i) b[i] ^= (1ll << (bit + 1));
			merge(b+1,b+j, b+j, b+n+1, c+1);
			//cout << j << "| ";
			for (int i = 1 ; i <= n ; ++ i) {
				b[i] = c[i];
			}
		}
		int parity = 0;
		sort(b+1,b+1+n);
		//for (int i = 1 ; i <= n ; ++ i) cout << b[i] << " \n"[i == n];
		for (int i = 1, l = n, r = n ; i <= n ; ++ i) {
			while (l >= 1 && (1<<bit) <= b[i] + b[l]) --l;
			while (r >= 1 && b[i] + b[r] > (1<<(bit+1))-1) --r;
			int cur = max(r,i) - max(l,i-1);
			if (r < i) break;
			if (cur & 1) parity ^= 1;
			//cout << i << " " << l + 1 << " " << r << "\n";
		}
		for (int i = 1, l = n, r = n ; i <= n ; ++ i) {
			while (l >= 1 && (1<<(bit+1))+(1<<bit) <= b[i] + b[l]) --l;
			while (r >= 1 && b[i] + b[r] > (1ll<<(bit+2))-1) --r;
			int cur = max(r,i) - max(l,i-1);
			if (r < i) break;
			if (cur & 1) parity ^= 1;
			//cout << i << " " << l + 1 << " " << r << "\n";
		}
		ans += parity * (1 << bit);
	}
	cout << ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 12208 KB Output is correct
2 Correct 830 ms 15596 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 12208 KB Output is correct
2 Correct 830 ms 15596 KB Output is correct
3 Correct 1100 ms 18924 KB Output is correct
4 Correct 1067 ms 18156 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 492 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 127 ms 1516 KB Output is correct
4 Correct 128 ms 1644 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 492 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 925 ms 12208 KB Output is correct
4 Correct 830 ms 15596 KB Output is correct
5 Correct 1100 ms 18924 KB Output is correct
6 Correct 1067 ms 18156 KB Output is correct
7 Correct 127 ms 1516 KB Output is correct
8 Correct 128 ms 1644 KB Output is correct
9 Correct 1299 ms 21436 KB Output is correct
10 Correct 1277 ms 21612 KB Output is correct
11 Correct 1288 ms 21612 KB Output is correct