Submission #1230561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230561		lopkus	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	619 ms	24028 KiB

xorsum

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;typedef long long ll; 
static const int BS=1<<17;char ibuf[BS];int ip,isz;
inline int gc(){if(ip==isz){isz=read(0,ibuf,BS);if(!isz)return EOF;ip=0;}return ibuf[ip++];}
inline ll R(){int c=gc();while(c!='-'&&(c<'0'||c>'9'))c=gc();bool neg=c=='-';if(neg)c=gc();ll r=0;while(c>='0'&&c<='9'){r=r*10+c-'0';c=gc();}return neg?-r:r;}
char obuf[BS];int op;
inline void flush(){write(1,obuf,op);op=0;}
inline void PC(char c){if(op==BS)flush();obuf[op++]=c;}
inline void W(ll x){if(x<0){PC('-');x=-x;}char s[21];int n=0;if(!x)s[n++]='0';else while(x){s[n++]=x%10+'0';x/=10;}while(n--)PC(s[n]);}
inline void WL(){PC('\n');}
inline void Radix(vector<ll>& v,int b){int n=v.size();vector<ll> t(n);const int B=8,mask=(1<<8)-1;for(int s=0;s<b;s+=B){int cnt[1<<8]={0};for(int i=0;i<n;i++)cnt[(v[i]>>s)&mask]++;for(int i=1;i<(1<<B);i++)cnt[i]+=cnt[i-1];for(int i=n;i--;){t[--cnt[(v[i]>>s)&mask]]=v[i];}v.swap(t);}}
int main(){int n=R();vector<ll> v(n);for(int i=0;i<n;i++)v[i]=R();vector<ll> bc(31,0);for(auto x:v)for(int j=0;j<31;j++)bc[j]+=((x>>j)&1);ll ans=0;vector<ll> mod(n);for(int i=0;i<31;i++){ll m=1LL<<(i+1),t1=1LL<<i,t2=m-1,t3=m+t1,t4=(m<<1)-2;for(int j=0;j<n;j++)mod[j]=v[j]& (m-1);Radix(mod,min(32,i+1));ll c=0;int p1=n,p2=n,p3=n,p4=n;for(auto x:mod){ll l1=t1-x,r1=t2-x;while(p1 && mod[p1-1]>=l1)p1--;while(p2 && mod[p2-1]>r1)p2--;c+=p2-p1;ll l2=t3-x,r2=t4-x;while(p3 && mod[p3-1]>=l2)p3--;while(p4 && mod[p4-1]>r2)p4--;c+=p4-p3;}ll d=(i?bc[i-1]:0);if(((c+d)>>1)&1)ans+=1LL<<i;}W(ans);WL();flush();return 0;}

Compilation message (stderr)

xorsum.cpp: In function 'void flush()':
xorsum.cpp:12:26: warning: ignoring return value of 'ssize_t write(int, const void*, size_t)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | inline void flush(){write(1,obuf,op);op=0;}
      |                     ~~~~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23