oj.uz

Submission #410484

# Submission time Handle Problem Language Result Execution time Memory
410484 2021-05-22T18:44:38 Z nichke XOR Sum (info1cup17_xorsum) C++14
100 / 100
 826 ms 57828 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
 
int n, res;
int ar[1000006];
int tar[1000006];

vector< pair<int, int> > tmp, cur;
 
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
		tmp.push_back({ar[i], 0});
	}
	for (int j = 0; j < 31; j++) {
		for (auto i : tmp) {
			if (i.first & (1 << j)) continue;
			cur.push_back(i);
		}
		for (auto i : tmp) {
			if (i.first & (1 << j)) {
				cur.push_back({i.first, i.second + (1 << j)});
			}
		}
		int p1, p2, p3, sum = 0;
		p1 = n - 1, p2 = n - 1, p3 = n - 1;
		for (int i = 0; i < n; i++) {
			p1 = max(p1, i - 1);
			p2 = max(p2, i - 1);
			p3 = max(p3, i - 1);
			while (p1 >= i && cur[i].second + cur[p1].second >= (1 << j)) p1--;
			while (p2 >= i && cur[i].second + cur[p2].second >= 2 * (1 << j)) p2--;
			while (p3 >= i && cur[i].second + cur[p3].second >= 3 * (1 << j)) p3--;
			sum += p2 - p1 + n - 1 - p3;
		}
		if (sum & 1) {
			res += (1 << j);
		}
		swap(tmp, cur);
		cur.clear();
	}
	cout << res << '\n';
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 48356 KB Output is correct
2 Correct 484 ms 51132 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 48356 KB Output is correct
2 Correct 484 ms 51132 KB Output is correct
3 Correct 643 ms 55076 KB Output is correct
4 Correct 612 ms 54032 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 5 ms 460 KB Output is correct
3 Correct 82 ms 5700 KB Output is correct
4 Correct 83 ms 5756 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 5 ms 460 KB Output is correct
3 Correct 520 ms 48356 KB Output is correct
4 Correct 484 ms 51132 KB Output is correct
5 Correct 643 ms 55076 KB Output is correct
6 Correct 612 ms 54032 KB Output is correct
7 Correct 82 ms 5700 KB Output is correct
8 Correct 83 ms 5756 KB Output is correct
9 Correct 808 ms 57828 KB Output is correct
10 Correct 813 ms 57720 KB Output is correct
11 Correct 826 ms 57744 KB Output is correct