Submission #67981

#TimeUsernameProblemLanguageResultExecution timeMemory
67981hamzqq9XOR Sum (info1cup17_xorsum)C++14
100 / 100
1563 ms40324 KiB
#include<bits/stdc++.h> #define st first #define nd second #define pb push_back #define ppb pop_back #define umax(x,y) x=max(x,y) #define umin(x,y) x=min(x,y) #define ll long long #define ii pair<int,int> #define iii pair<int,ii> #define sz(x) ((int) x.size()) #define orta ((bas+son)>>1) #define all(x) x.begin(),x.end() #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define pw(x) (1<<(x)) #define inf 1000000000000000000 #define MOD 1000000007 #define N 1000006 #define MAX 10000006 #define LOG 30 using namespace std; int n,ans,a[N]; ii ar[2][N]; int main() { // freopen("input.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); ar[0][i-1]={a[i]&1,i}; } sort(ar[0],ar[0]+n); for(int i=0;i<LOG;i++) { int cp=pw(i); int cpp=pw(i+1); int cppp=pw(i+2); int bas=n,son=n-1; bool ok=0; int cur=i&1; for(int j=0;j<n;j++) { while(son>=0 && ar[cur][son].st+ar[cur][j].st>cpp-1) son--; while(bas-1>=0 && ar[cur][bas-1].st+ar[cur][j].st>=cp) bas--; if(son<j) break ; ok^=max(0,(son-max(j,bas)+1))&1; } bas=n,son=n-1; for(int j=0;j<n;j++) { while(son>=0 && ar[cur][son].st+ar[cur][j].st>cppp-2) son--; while(bas-1>=0 && ar[cur][bas-1].st+ar[cur][j].st>=cpp+cp) bas--; if(son<j) break ; ok^=max(0,(son-max(j,bas)+1))&1; } if(ok) ans+=pw(i); int now=0; int oth=1^cur; for(int j=0;j<n;j++) if(!(a[ar[cur][j].nd]&cpp)) ar[oth][now++]=ar[cur][j]; for(int j=0;j<n;j++) if(a[ar[cur][j].nd]&cpp) ar[oth][now++]={ar[cur][j].st+cpp,ar[cur][j].nd}; } printf("%d",ans); }

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
xorsum.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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...