Submission #440971

#TimeUsernameProblemLanguageResultExecution timeMemory
440971zxcvbnmXOR Sum (info1cup17_xorsum)C++14
100 / 100
802 ms31508 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(); } // sudedame du surikiuotus masyvus i viena, islaikydami nemazejancia tvarka int id1 = 0, id2 = 0; n = a.size(); int m = b.size(); while(id1 < n && id2 < m) { // visada galime deti mazesni elementa nesugadindami tvarkos if (a[id1] < b[id2]) { c.push_back(a[id1++]); } else { c.push_back(b[id2++]); } } // jei dar liko elementu is a while(id1 < n) { c.push_back(a[id1++]); } // jei dar liko elementu is b 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); } int pos1 = n, pos2 = n, pos3 = n; 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 && 1*p[j]-x[i] <= x[pos1-1]) pos1--; while(pos2 >= i+1 && 2*p[j]-x[i] <= x[pos2-1]) pos2--; while(pos3 >= i+1 && 3*p[j]-x[i] <= x[pos3-1]) 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...