Submission #518324

#	Time	Username	Problem	Language	Result	Execution time	Memory
518324		lucri	XOR Sum (info1cup17_xorsum)	C++17	0 / 100	504 ms	13148 KiB

xorsum

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

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