Submission #141197

#TimeUsernameProblemLanguageResultExecution timeMemory
141197meatrowXOR Sum (info1cup17_xorsum)C++17
100 / 100
754 ms11148 KiB
//#pragma GCC optimize("O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") //#pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int M = 30; const int N = 1e6; int a[N]; int k[2]; int y[2][N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int ans = 0; int pw = 1; for (int b = 0; b < M; b++) { int q = (pw << 1) - 1; int kek = 0; k[0] = k[1] = 0; for (int i = 0; i < n; i++) { y[(a[i] >> b) & 1][k[(a[i] >> b) & 1]++] = a[i]; } int p = 0; for (int i = 0; i < 2; i++) { memcpy(a + p, y[i], sizeof(int) * k[i]); p += k[i]; } int it1 = n - 1; int it2 = n - 1; int it3 = n - 1; for (int i = 0; i < n; i++) { int t = a[i] & q; while (it1 >= 0 && (a[it1] & q) >= pw - t) { it1--; } while (it2 >= 0 && (a[it2] & q) > q - t) { it2--; } while (it3 >= 0 && (a[it3] & q) >= 3 * pw - t) { it3--; } (kek += max(0, min(it2, i) - it1)) &= 1; if (t & pw) { (kek += max(0, i - it3)) &= 1; } } if (kek) { ans += pw; } pw <<= 1; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...