Submission #518328

#	Time	Username	Problem	Language	Result	Execution time	Memory
518328		lucri	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	810 ms	17848 KiB

xorsum

#include <iostream>
#include <algorithm>
using namespace std;
long long ans,pdoi[35],nr[1000010],n;
long long cb(long long s,long long b,long long e)
{
    if(b>e)
        return b;
    long long m=(b+e)/2;
    if(nr[1]+nr[m]<s)
        return cb(s,m+1,e);
    return cb(s,b,m-1);
}
long long v[1000010];
void ms(long long x)
{
    for(long long i=1;i<x;++i)
        v[i]=nr[i];
    long long a=1,b=x,c=0;
    while(a<x&&b<=n)
    {
        if(v[a]<nr[b])
        {
            nr[++c]=v[a];
            ++a;
        }
        else
        {
            nr[++c]=nr[b];
            ++b;
        }
    }
    while(a<x)
        nr[++c]=v[a++];
    while(b<=n)
        nr[++c]=nr[b++];
    return;
}
int main()
{
    cin>>n;
    pdoi[0]=1;
    for(long long i=1;i<=30;++i)
        pdoi[i]=pdoi[i-1]*2;
    for(long long i=1;i<=n;++i)
        cin>>nr[i];
    sort(nr+1,nr+n+1);
    for(long long i=29;i>=0;--i)
    {
        long long p1=cb(pdoi[i],1,n);
        long long p2=cb(pdoi[i+1],1,n);
        long long p3=cb(pdoi[i+1]+pdoi[i],1,n);
        if((p2-p1+n+1-p3)%2==1)
            ans^=pdoi[i];
        for(long long j=2;j<=n;++j)
        {
            while(p1>=j&&nr[j]+nr[p1-1]>=pdoi[i])
                --p1;
            while(p2>=j&&nr[j]+nr[p2-1]>=pdoi[i+1])
                --p2;
            while(p3>=j&&nr[j]+nr[p3-1]>=pdoi[i]+pdoi[i+1])
                --p3;
            if(p1<j)
                ++p1;
            if(p2<j)
                ++p2;
            if(p3<j)
                ++p3;
            if((p2-p1+n+1-p3)%2==1)
                ans^=pdoi[i];
        }
        long long nrm=n+1;
        while(nr[--nrm]>=pdoi[i])
        {
            nr[nrm]-=pdoi[i];
        }
        ms(nrm+1);
    }
    cout<<ans;
    return 0;
}

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