oj.uz

Submission #518324

# Submission time Handle Problem Language Result Execution time Memory
518324 2022-01-23T11:26:11 Z lucri XOR Sum (info1cup17_xorsum) C++17
0 / 100
 504 ms 13148 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 504 ms 13148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 504 ms 13148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -