Submission #373510

#TimeUsernameProblemLanguageResultExecution timeMemory
373510qpwoeirutXOR Sum (info1cup17_xorsum)C++17
77 / 100
1696 ms73884 KiB
//xorsum.cpp created at 03/04/21 10:30:22 #include <bits/stdc++.h> using namespace std; #define LB lower_bound const int MN = 1000000; const int LG = 23; int N; int A[MN]; int val[MN]; int psum[(1 << (LG + 1)) + 1]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> N; for (int i=0; i<N; ++i) { cin >> A[i]; } sort(A, A+N); int ans = 0; for (int i=0; i<LG; ++i) { fill(psum, psum + (1 << (i+2)) + 1, 0); for (int j=0; j<N; ++j) { ++psum[(A[j] & ((1 << (i + 1)) - 1)) + 1]; // add 1 for easy indexing stuff } for (int j=1; j<=(1 << (i+2)); ++j) { psum[j] += psum[j - 1]; } // range [2^i, 2^(i+1)) and [2^(i+1) + 2^i, 2^(i+2)) int ct = 0; for (int j=0; j<N; ++j) { const int cur = A[j] & ((1 << (i + 1)) - 1); const int lo1 = (1 << i) - cur; ct += psum[(1 << (i + 1)) - cur] - psum[lo1 < 0 ? 0 : lo1] + psum[(1 << (i + 2)) - cur] - psum[(1 << (i + 1)) + lo1] + (((A[j] << 1) >> i) & 1); } ans |= (i == 0) ? ((ct >> 1) & 1) : ((ct & 2) << (i-1)); } for (int i=LG; i<30; ++i) { for (int j=0; j<N; ++j) { val[j] = A[j] & ((1 << (i + 1)) - 1); } sort(val, val+N); int ct = 0; for (int j=0; j<N; ++j) { const int cur = A[j] & ((1 << (i + 1)) - 1); const int range1 = LB(val, val+N, (1 << (i + 1)) - cur) - LB(val, val+N, (1 << i) - cur); const int range2 = LB(val, val+N, (1LL << (i + 2)) - cur) - LB(val, val+N, (1 << (i + 1)) + (1 << i) - cur); ct += range1 + range2 + ((A[j] >> (i-1)) & 1); } ans |= (ct & 2) << (i-1); } cout << ans << '\n'; } /* 4 3 9 6 6 00110 1 1 01100 1 2 01001 1 3 01001 1 4 10010 2 2 01111 2 3 01111 2 4 01100 3 3 01100 3 4 01100 4 4 */
#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...