Submission #68034

#TimeUsernameProblemLanguageResultExecution timeMemory
68034top34051XOR Sum (info1cup17_xorsum)C++17
100 / 100
1238 ms36060 KiB
#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 (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
xorsum.cpp:14:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~
#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...