#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pp;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
int _mx = 0;
vector<int> a(n);
for (int &i : a) cin >> i, _mx = max(_mx, i);
int ans = 0;
for (int i = 0; i < 30; ++i) {
vector<int> v[2], q, q2;
for (int j : a) v[j >> i & 1].push_back(j);
int it = 0;
for (int j : v[0]) a[it++] = j;
for (int j : v[1]) a[it++] = j;
int x = (1 << i + 1) - 1;
ll tmp = 0;
for (int j : v[1]) {
j &= x;
if (j << 1 & 1 << i) ++tmp;
q.push_back(x - j);//+
q2.push_back(x + (1 << i) - j);//-
tmp += (int)v[1].size();
}
for (int j = 0; j <= v[0].size(); ++j)
while (!q.empty() && (j == v[0].size() || q.back() < (v[0][j] & x))) tmp += j, q.pop_back();
for (int j = 0; j <= v[1].size(); ++j)
while (!q2.empty() && (j == v[1].size() || q2.back() < (v[1][j] & x))) tmp -= j, q2.pop_back();
for (int j : v[0]) {
j &= x;
if (j << 1 & 1 << i) ++tmp;
q.push_back(x - j);//+
q2.push_back((x >> 1) - j);//-
tmp += (int)v[0].size();
}
for (int j = 0; j <= v[1].size(); ++j)
while (!q.empty() && (j == v[1].size() || q.back() < (v[1][j] & x))) tmp += j, q.pop_back();
for (int j = 0; j <= v[0].size(); ++j)
while (!q2.empty() && (j == v[0].size() || q2.back() < (v[0][j] & x))) tmp -= j, q2.pop_back();
if (tmp & 2) ans ^= 1 << i;
}
cout << ans;
}
Compilation message
xorsum.cpp: In function 'int main()':
xorsum.cpp:32:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
32 | int x = (1 << i + 1) - 1;
| ~~^~~
xorsum.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int j = 0; j <= v[0].size(); ++j)
| ~~^~~~~~~~~~~~~~
xorsum.cpp:42:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | while (!q.empty() && (j == v[0].size() || q.back() < (v[0][j] & x))) tmp += j, q.pop_back();
| ~~^~~~~~~~~~~~~~
xorsum.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int j = 0; j <= v[1].size(); ++j)
| ~~^~~~~~~~~~~~~~
xorsum.cpp:44:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | while (!q2.empty() && (j == v[1].size() || q2.back() < (v[1][j] & x))) tmp -= j, q2.pop_back();
| ~~^~~~~~~~~~~~~~
xorsum.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int j = 0; j <= v[1].size(); ++j)
| ~~^~~~~~~~~~~~~~
xorsum.cpp:53:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (!q.empty() && (j == v[1].size() || q.back() < (v[1][j] & x))) tmp += j, q.pop_back();
| ~~^~~~~~~~~~~~~~
xorsum.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int j = 0; j <= v[0].size(); ++j)
| ~~^~~~~~~~~~~~~~
xorsum.cpp:55:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | while (!q2.empty() && (j == v[0].size() || q2.back() < (v[0][j] & x))) tmp -= j, q2.pop_back();
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
892 ms |
22160 KB |
Output is correct |
| 2 |
Correct |
834 ms |
21328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
892 ms |
22160 KB |
Output is correct |
| 2 |
Correct |
834 ms |
21328 KB |
Output is correct |
| 3 |
Correct |
928 ms |
22168 KB |
Output is correct |
| 4 |
Correct |
884 ms |
21764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
404 KB |
Output is correct |
| 3 |
Correct |
109 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
111 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
404 KB |
Output is correct |
| 3 |
Correct |
892 ms |
22160 KB |
Output is correct |
| 4 |
Correct |
834 ms |
21328 KB |
Output is correct |
| 5 |
Correct |
928 ms |
22168 KB |
Output is correct |
| 6 |
Correct |
884 ms |
21764 KB |
Output is correct |
| 7 |
Correct |
109 ms |
2648 KB |
Output is correct |
| 8 |
Correct |
111 ms |
2636 KB |
Output is correct |
| 9 |
Correct |
1089 ms |
22244 KB |
Output is correct |
| 10 |
Correct |
1076 ms |
22284 KB |
Output is correct |
| 11 |
Correct |
1082 ms |
22188 KB |
Output is correct |
