Submission #162219

#TimeUsernameProblemLanguageResultExecution timeMemory
162219mrtsima22XOR Sum (info1cup17_xorsum)C++17
100 / 100
1419 ms44992 KiB
#pragma GCC optimize "-O3" #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define two pair<int,int> #define pb push_back #define f first #define s second #define sz(container) (int)(container.size()) 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; two a[1000004],b[1000004]; two v0[1000004],v1[1000004]; two v[1000004]; int c[39],ans,n,d[39]; 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].f+b[o].f<x) l++; while(r+1<n&&b[r+1].f+b[o].f<=y) r++; if(o>l&&o<=r) K++; if(l<=r) k+=(r-l); } } int main(){ for(int i=1;i<=M;i++){ c[i]=(1<<(i+1))-1; d[i]=(1<<(i)); } n=bin(); for(int i=0;i<n;i++){ a[i].f=bin(); a[i].s=i; } for(int i=1;i<=M;i++){ if(i==1){ for(int j=0;j<n;j++){ b[j].f=c[i]&a[j].f; b[j].s=a[j].s; } sort(b,b+n); }else{ for(int j=0;j<n;j++){ b[j].f=b[j].f&c[i]; } int V1=0,V0=0; for(int j=0;j<n;j++){ if(d[i]&b[j].f){ v1[V1]=b[j]; V1++; }else{ v0[V0]=b[j]; V0++; } } for(int j=0;j<V0;j++){ v[j]=v0[j]; } for(int j=0;j<V1;j++){ v[j+V0]=v1[j]; } for(int j=0;j<n;j++){ b[j]=v[j]; } } 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)); } for(int j=0;j<n;j++){ b[j].f=a[b[j].s].f; } } int k=0; for(int i=0;i<n;i++){ if(a[i].f&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...