Submission #1092479

#TimeUsernameProblemLanguageResultExecution timeMemory
1092479pubin06XOR Sum (info1cup17_xorsum)C++14
45 / 100
1651 ms12664 KiB
#include <bits/stdc++.h> #define fi first #define se second #define sz(v) (int)(v).size() using namespace std; const int MXn = 1000005; const long long oo = 1e18; const int MOD = 1e9 + 7; int N, a[MXn], t[MXn]; signed main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N; for (int i = 1; i <= N; i++) cin >> a[i]; int mask = 0; int ans = 0; for (int k = 0; k < 30; k++) { mask |= (1 << k); for (int i = 1; i <= N; i++) t[i] = a[i] & mask; sort(t + 1, t + 1 + N); int p1 = N, p2 = N, p3 = N; int cnt = 0; // [2^k, 2^(k+1) - 1]; [2^(k+1) + 2^k, 2^(k+2) - 2] // cerr << (1 << k) << ' ' << ((1 << (k + 1)) - 1) << ' ' << ((1 << (k + 1)) + (1 << k)) << ' ' << ((1 << (k + 2)) - 2) << ' '; // cerr << "[ "; // for (int i = 1; i <= N; i++) { // cerr << t[i] << ' '; // } // cerr << "] "; for (int i = 1; i <= N; i++) { p1 = lower_bound(t + i, t + 1 + N, (1 << k) - t[i]) - t; p2 = lower_bound(t + i, t + 1 + N, (1 << (k + 1)) - t[i]) - t; p3 = lower_bound(t + i, t + 1 + N, (1 << (k + 1)) + (1 << k) - t[i]) - t; // while (t[i] + t[p1] > (1 << k) && p1 >= i) p1--; // while (t[i] + t[p2] >= (1 << (k + 1)) && p2 >= i) p2--; // while (t[i] + t[p3] >= ((1 << (k + 1)) + (1 << k)) && p3 >= i) p3--; cnt += (p2 - p1) + (N - max(i, p3 + 1) + 1); // cerr << "(" << p1 << ' ' << p2 << ' ' << p3 << ")"; // cnt &= 1; } // cerr << ' ' << cnt << '\n'; cnt &= 1; ans += (cnt << k); } cout << ans; return 0; } /* 00011 01001 00110 00110 */
#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...