Submission #373501

#TimeUsernameProblemLanguageResultExecution timeMemory
373501qpwoeirutXOR Sum (info1cup17_xorsum)C++17
32 / 100
497 ms19180 KiB
//xorsum.cpp created at 03/04/21 10:30:22 #include <bits/stdc++.h> using namespace std; const int MN = 1000006; const int LG = 21; int N; int A[MN]; int psum[(1 << LG) + 1]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> N; for (int i=0; i<N; ++i) { cin >> A[i]; assert(A[i] < (1 << (LG - 1))); } int ans = 0; for (int i=0; i<LG; ++i) { fill(psum, psum + (1 << LG) + 1, 0); for (int j=0; j<N; ++j) { const int val = A[j] & ((1 << (i + 1)) - 1); ++psum[val + 1]; // add 1 for easy indexing stuff } for (int j=1; j<=(1 << LG); ++j) { psum[j] += psum[j - 1]; } //cerr << "psum:"; for (int j=1; j<=10; ++j) { cerr << ' ' << psum[j]; } cerr << endl; // 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) { //cerr << "start: " << i << ' ' << j << ' ' << ct << endl; const int val = A[j] & ((1 << (i + 1)) - 1); const int lo1 = max(0, (1 << i) - val); const int hi1 = (1 << (i + 1)) - val; ct += psum[hi1] - psum[lo1]; //cerr << "range1: " << i << ' ' << j << ' ' << ct << endl; const int lo2 = min(1 << LG, (1 << (i + 1)) + (1 << i) - val); const int hi2 = min(1 << LG, (1 << (i + 2)) - val); ct += psum[hi2] - psum[lo2]; //cerr << "range2: " << i << ' ' << j << ' ' << ct << endl; ct += ((A[j] << 1) >> i) & 1; //cerr << "dupe: " << i << ' ' << j << ' ' << ct << endl; } //cerr << i << ' ' << ct << endl; assert((ct & 1) == 0); ct = (ct >> 1) & 1; ans += ct << i; } 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...