# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
68034 | 2018-08-15T19:35:11 Z | top34051 | XOR Sum (info1cup17_xorsum) | C++17 | 1238 ms | 36060 KB |
#include<bits/stdc++.h> using namespace std; #define X first #define Y second const int maxn = 1e6 + 5; const int mlog = 29; int n; int a[maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ans = 0; vector<pair<int,int>> b[2]; for(int i=1;i<=n;i++) b[0].push_back({0,a[i]}); for(int i=0;i<=mlog;i++) { int pw = (1<<i); // printf("pw = %d\n",pw); vector<pair<int,int>> tmp[2]; for(auto t : b[0]) { int x = t.second; tmp[(x/pw)%2].push_back({x%pw,x}); } for(auto t : b[1]) { int x = t.second; tmp[(x/pw)%2].push_back({x%pw,x}); } b[0] = tmp[0]; b[1] = tmp[1]; int sz0 = b[0].size(); int sz1 = b[1].size(); // printf("\t"); // for(auto t : b[0]) printf("%d ",t); // printf("\n"); // printf("\t"); // for(auto t : b[1]) printf("%d ",t); // printf("\n"); long long cnt1 = 0, cnt2 = 0, cnt3 = 0; //tx = 0 ty = 0 //2^i <= b[x] + b[y] (< 2^(i+1)) for(int x=0,y=sz0;x<sz0;++x) { while(y-1 >= 0 && pw <= b[0][x].X + b[0][y-1].X) --y; cnt1 += sz0-y; } for(auto t : b[0]) if(pw <= t.X*2) cnt1++; cnt1 /= 2; //tx = 0 ty = 1 //b[x] + b[y] < 2^i for(int x=sz0-1,y=-1;x>=0;--x) { while(y+1 < sz1 && b[0][x].X + b[1][y+1].X < pw) ++y; cnt2 += y+1; } //tx = 1 ty = 1 //2^i <= b[x] + b[y] (< 2^(i+1)) for(int x=0,y=sz1;x<sz1;++x) { while(y-1 >= 0 && pw <= b[1][x].X + b[1][y-1].X) --y; cnt3 += sz1-y; } for(auto t : b[1]) if(pw <= t.X*2) cnt3++; cnt3 /= 2; if((cnt1+cnt2+cnt3)&1) ans += pw; } printf("%d",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 504 KB | Output is correct |
2 | Correct | 7 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1060 ms | 35872 KB | Output is correct |
2 | Correct | 995 ms | 35872 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1060 ms | 35872 KB | Output is correct |
2 | Correct | 995 ms | 35872 KB | Output is correct |
3 | Correct | 1081 ms | 35872 KB | Output is correct |
4 | Correct | 978 ms | 35872 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 504 KB | Output is correct |
2 | Correct | 7 ms | 504 KB | Output is correct |
3 | Correct | 106 ms | 35872 KB | Output is correct |
4 | Correct | 112 ms | 35872 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 504 KB | Output is correct |
2 | Correct | 7 ms | 504 KB | Output is correct |
3 | Correct | 1060 ms | 35872 KB | Output is correct |
4 | Correct | 995 ms | 35872 KB | Output is correct |
5 | Correct | 1081 ms | 35872 KB | Output is correct |
6 | Correct | 978 ms | 35872 KB | Output is correct |
7 | Correct | 106 ms | 35872 KB | Output is correct |
8 | Correct | 112 ms | 35872 KB | Output is correct |
9 | Correct | 1238 ms | 35872 KB | Output is correct |
10 | Correct | 1142 ms | 36060 KB | Output is correct |
11 | Correct | 1160 ms | 36060 KB | Output is correct |