# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
128663 | E869120 | XOR Sum (info1cup17_xorsum) | C++14 | 1090 ms | 106568 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)
const int THRESHOLD = 23;
int N, A[1 << 20], S[1 << 24], V[1 << 21];
pair<int, int> U[1 << 20];
pair<int, int> U0[1 << 20];
pair<int, int> U1[1 << 20];
void making(int bit) {
if (bit == THRESHOLD) {
int TEISUU = (2 << bit) - 1;
for (int i = 1; i <= N; i++) U[i - 1] = make_pair((A[i] & TEISUU), i);
sort(U, U + N);
}
else {
int c1 = 0, c2 = 0, TEISUU = (2 << bit) - 1;
for (int i = 0; i < N; i++) {
if ((A[U[i].second] & TEISUU) < (1 << bit)) { U0[c1] = make_pair((A[U[i].second] & TEISUU), U[i].second); c1++; }
if ((A[U[i].second] & TEISUU) >= (1 << bit)) { U1[c2] = make_pair((A[U[i].second] & TEISUU), U[i].second); c2++; }
}
for (int i = 0; i < c1; i++) U[i] = U0[i];
for (int i = 0; i < c2; i++) U[i + c1] = U1[i];
}
for (int i = 0; i < N; i++) V[i] = U[i].first;
for (int i = 0; i < N; i++) V[i + N] = V[i] + (2 << bit);
}
int solve(int bit) {
if (bit <= THRESHOLD - 1) {
for (int i = 0; i < (4 << bit); i++) S[i] = 0;
long long sum = 0; int TEISUU = (2 << bit);
for (int i = 1; i <= N; i++) {
S[A[i] & (TEISUU - 1)]++;
S[(A[i] & (TEISUU - 1)) + TEISUU]++;
}
for (int i = 1; i < (4 << bit); i++) S[i] += S[i - 1];
for (int i = 1; i <= N; i++) {
int F = (3 << bit) - (A[i] & (TEISUU - 1)); F &= (TEISUU - 1);
int pos1 = 0; if (F >= 1) pos1 = S[F - 1];
int pos2 = 0; if (F + (1 << bit) >= 1) pos2 = S[(F + (1 << bit)) - 1];
sum += 1LL * (pos2 - pos1);
}
long long sum2 = 0;
for (int i = 1; i <= N; i++) {
if (((A[i] + A[i]) & (TEISUU - 1)) >= (1 << bit)) sum2++;
}
return (sum2 + (sum - sum2) / 2LL) % 2LL;
}
else {
making(bit); int TEISUU = (2 << bit); long long sum = 0;
int c1 = 0, c2 = 0;
for (int i = N - 1; i >= 0; i--) {
int F1 = (3 << bit) - (U[i].first & (TEISUU - 1));
int F2 = (4 << bit) - (U[i].first & (TEISUU - 1));
while (c1 < N * 2 && V[c1] < F1) c1++;
while (c2 < N * 2 && V[c2] < F2) c2++;
sum += 1LL * (c2 - c1);
}
long long sum2 = 0;
for (int i = 1; i <= N; i++) {
if (((A[i] + A[i]) & (TEISUU - 1)) >= (1 << bit)) sum2++;
}
return (sum2 + (sum - sum2) / 2LL) % 2LL;
}
}
int main() {
scanf("%d", &N); int maxn = 0;
for (int i = 1; i <= N; i++) { scanf("%d", &A[i]); maxn = max(maxn, A[i]); }
int P = 0; for (int i = 0; i <= 30; i++) { if ((1 << i) <= maxn) P = i; }
int ans = 0;
for (int i = 0; i <= min(29, P + 1); i++) {
int t = solve(i);
if (t == 1) ans += (1 << i);
}
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |