Submission #159363

#TimeUsernameProblemLanguageResultExecution timeMemory
159363mrtsima22XOR Sum (info1cup17_xorsum)C++17
45 / 100
1652 ms8184 KiB
#pragma GCC optimize "-O3" #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; inline int bin(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x; } const int M=29; int n,a[1000004],b[1000004]; int c[39],ans; inline void work(int x,int y,int &k,int &K){ int l=-1,r=-1; for(int o=n-1;o>=0;o--){ while(l+1<n&&b[l+1]+b[o]<x) l++; while(r+1<n&&b[r+1]+b[o]<=y) r++; if(o>l&&o<=r) K++; if(l<=r) k+=(r-l); } } int main(){ ios::sync_with_stdio(false); for(int i=1;i<=M;i++){ c[i]=(1<<(i+1))-1; } n=bin(); for(int i=0;i<n;i++){ a[i]=bin(); } for(int i=1;i<=M;i++){ for(int j=0;j<n;j++){ b[j]=c[i]&a[j]; } sort(b,b+n); int b1=(1<<(i)); int b2=((1<<(i+1))-1); int B1=b1+(1<<(i+1)); int B2=((1<<(i+2))-2); int k=0,K=0; work(b1,b2,k,K); work(B1,B2,k,K); k-=K; k/=2; k+=K; if(k&1){ ans|=(1<<(i)); } } int k=0; for(int i=0;i<n;i++){ if(a[i]&1) k++; } if((k*(n-k))&1){ ans++; } cout<<ans<<endl; }
#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...