# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
45673 | 2018-04-16T02:03:09 Z | aome | XOR Sum (info1cup17_xorsum) | C++17 | 1317 ms | 56396 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1000005; int n; int res; int a[N]; int b[N]; bool p[35][N]; int arr[N]; int f[2][N]; int buf[2][N]; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); for (int j = 0; j < 30; ++j) { p[j][i] = a[i] >> j & 1; } } for (int i = 0; i < n; ++i) arr[i] = i; for (int i = 0; i <= 30; ++i) { // cout << "#\n"; // for (int j = 0; j < n; ++j) cout << arr[j] << ' ' << b[arr[j]] << '\n'; for (int j = n - 1; j >= 0; --j) { f[0][j] = f[0][j + 1], f[1][j] = f[1][j + 1]; f[p[i][arr[j]]][j]++; } int cur = 0, ptr = n; int cnt[2]; cnt[0] = cnt[1] = 0; for (int j = 0; j < n; ++j) { if (ptr < j) { cnt[p[i][arr[ptr]]]--, ptr++; } while (ptr > j && b[arr[ptr - 1]] + b[arr[j]] >= (1 << i)) { ptr--, cnt[p[i][arr[ptr]]]++; } int cnt2[2]; cnt2[0] = f[0][j] - cnt[0]; cnt2[1] = f[1][j] - cnt[1]; cur ^= cnt[p[i][arr[j]]] & 1; cur ^= cnt2[p[i][arr[j]] ^ 1] & 1; } res += cur << i; if (i == 30) break; int sz[2]; sz[0] = sz[1] = 0; for (int j = 0; j < n; ++j) { b[j] += p[i][j] << i; } for (int j = 0; j < n; ++j) { bool x = p[i][arr[j]]; buf[x][sz[x]++] = arr[j]; } for (int j = 0; j < sz[0]; ++j) { arr[j] = buf[0][j]; } for (int j = 0; j < sz[1]; ++j) { arr[j + sz[0]] = buf[1][j]; } } cout << res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 760 KB | Output is correct |
2 | Correct | 6 ms | 868 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1193 ms | 56184 KB | Output is correct |
2 | Correct | 1031 ms | 56184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1193 ms | 56184 KB | Output is correct |
2 | Correct | 1031 ms | 56184 KB | Output is correct |
3 | Correct | 1144 ms | 56356 KB | Output is correct |
4 | Correct | 1144 ms | 56356 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 760 KB | Output is correct |
2 | Correct | 6 ms | 868 KB | Output is correct |
3 | Correct | 127 ms | 56356 KB | Output is correct |
4 | Correct | 132 ms | 56356 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 760 KB | Output is correct |
2 | Correct | 6 ms | 868 KB | Output is correct |
3 | Correct | 1193 ms | 56184 KB | Output is correct |
4 | Correct | 1031 ms | 56184 KB | Output is correct |
5 | Correct | 1144 ms | 56356 KB | Output is correct |
6 | Correct | 1144 ms | 56356 KB | Output is correct |
7 | Correct | 127 ms | 56356 KB | Output is correct |
8 | Correct | 132 ms | 56356 KB | Output is correct |
9 | Correct | 1212 ms | 56356 KB | Output is correct |
10 | Correct | 1208 ms | 56396 KB | Output is correct |
11 | Correct | 1317 ms | 56396 KB | Output is correct |