oj.uz

Submission #676025

# Submission time Handle Problem Language Result Execution time Memory
676025 2022-12-29T00:23:22 Z thiago_bastos XOR Sum (info1cup17_xorsum) C++17
100 / 100
 674 ms 17460 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;

const int N = 1e6 + 10;

int v[N], tmp[N], n;

void solve() {
	int mx = 0, ans = 0;

	cin >> n;

	for(int i = 0; i < n; ++i) {
		cin >> v[i];
		mx = max(mx, v[i]);
	}

	mx <<= 1;

	int lg = 0;

	while((1 << lg) <= mx) ++lg;

	sort(v, v + n);

	for(int i = lg - 1; i >= 0; --i) {
		int lo[2] = {n, n}, hi[2] = {n, n};
		int L[2] = {1<<i, (1<<i)+(1<<(i+1))}, U[2] = {(1<<(i+1))-1, (1<<(i+2))-1};
		int pairs = 0, mask = (1 << (i + 1)) - 1;

		int k = 0, mid = 0, l = 0;

		while(mid < n && ~v[mid] & (1 << (i + 1))) ++mid;

		for(int i = 0; i < n; ++i) v[i] &= mask;

		int j = mid;

		while(k < mid && j < n) tmp[l++] = v[k] < v[j] ? v[k++] : v[j++];

		while(k < mid) tmp[l++] = v[k++];

		while(j < n) tmp[l++] = v[j++];

		memcpy(v, tmp, sizeof(int) * n);

		for(int j = 0; j < n; ++j) {
			for(int k = 0; k < 2; ++k) {
				while(hi[k] && v[j] + v[hi[k] - 1] > U[k]) --hi[k];
				while(lo[k] && v[j] + v[lo[k] - 1] >= L[k]) --lo[k];
				pairs ^= max(0, hi[k] - max(j, lo[k]));
			}
		}

		ans ^= (pairs & 1) * (1 << i);
	}

	cout << ans << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 8128 KB Output is correct
2 Correct 222 ms 11916 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 8128 KB Output is correct
2 Correct 222 ms 11916 KB Output is correct
3 Correct 413 ms 14856 KB Output is correct
4 Correct 383 ms 14344 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 72 ms 2004 KB Output is correct
4 Correct 72 ms 2044 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 231 ms 8128 KB Output is correct
4 Correct 222 ms 11916 KB Output is correct
5 Correct 413 ms 14856 KB Output is correct
6 Correct 383 ms 14344 KB Output is correct
7 Correct 72 ms 2004 KB Output is correct
8 Correct 72 ms 2044 KB Output is correct
9 Correct 674 ms 17456 KB Output is correct
10 Correct 665 ms 17452 KB Output is correct
11 Correct 667 ms 17460 KB Output is correct