Submission #440963

#TimeUsernameProblemLanguageResultExecution timeMemory
440963zxcvbnmXOR Sum (info1cup17_xorsum)C++14
0 / 100
1670 ms84936 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int L = 29; vector<int> p = {1}; vector<int> merge(vector<int> a, int pw) { vector<int> b, c; int n = a.size(); int id = n; for(int i = 0; i < n; i++) { if (a[i] >= p[pw+1]) { id = i; break; } } for(int i = id; i < n; i++) { a[i] -= p[pw+1]; b.push_back(a[i]); } for(int i = id; i < n; i++) { a.pop_back(); } int id1 = 0, id2 = 0; n = a.size(); int m = b.size(); while(id1 < n && id2 < m) { if (a[id1] < b[id2]) { c.push_back(a[id1++]); } else { c.push_back(b[id2++]); } } while(id1 < n) { c.push_back(a[id1++]); } while(id2 < m) { c.push_back(b[id2++]); } return c; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } for(int i = 1; i <= L+1; i++) { p.push_back(p[i-1]*2); } vector<int> cnt(L+1, 0); vector<int> x(n); for(int j = L; j >= 0; j--) { if (j == L) { for(int i = 0; i < n; i++) { x[i] = (a[i] % p[j+1]); } sort(x.begin(), x.end()); } else { x = merge(x, j); } for(int i : x) { cout << i << " "; } cerr << "\n"; int pos1 = n-1, pos2 = n-1, pos3 = n-1; for(int i = 0; i < n; i++) { pos1 = max(pos1, i-1); pos2 = max(pos2, i-1); pos3 = max(pos3, i-1); while(pos1 >= i && 1*p[j]-x[i] <= x[pos1]) pos1--; while(pos2 >= i && 2*p[j]-x[i] <= x[pos2]) pos2--; while(pos3 >= i && 3*p[j]-x[i] <= x[pos3]) pos3--; // pos1++, pos2++, pos3++; int curr = (pos2 - pos1) + (n - pos3); cnt[j] += curr; } } ll ans = 0; for(int i = 0; i <= L; i++) { // cout << cnt[i] << " "; if (cnt[i] % 2) { ans += p[i]; } } cout << ans << "\n"; 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...