Submission #440901

#TimeUsernameProblemLanguageResultExecution timeMemory
440901zxcvbnmXOR Sum (info1cup17_xorsum)C++14
45 / 100
1683 ms8200 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int L = 29; 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]; } vector<int> p = {1}; for(int i = 1; i <= L+1; i++) { p.push_back(p[i-1]*2); } vector<int> cnt(L+1, 0); for(int j = L; j >= 0; j--) { vector<int> x(n); // cout << j << " " << p[j] << "\n"; for(int i = 0; i < n; i++) { x[i] = (a[i] % p[j+1]); } sort(x.begin(), x.end()); for(int i = 0; i < n; i++) { int pos1, pos2, pos3; pos1 = lower_bound(x.begin(), x.end(), p[j]-x[i]) - x.begin(); pos2 = lower_bound(x.begin(), x.end(), 2*p[j]-x[i]) - x.begin(); pos3 = lower_bound(x.begin(), x.end(), 3*p[j]-x[i]) - x.begin(); assert(pos1 <= pos2 && pos2 <= pos3); int curr = (pos2 - pos1) + (n - pos3); if ((x[i] + x[i]) & p[j]) curr++; // cout << j << " " << i << " " << pos1 << " " << pos2 << " " << pos3 << "\n"; cnt[j] += curr; } } ll ans = 0; for(int i = 0; i <= L; i++) { cnt[i] /= 2; // cout << cnt[i] << "\n"; 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...