oj.uz

Submission #518328

# Submission time Handle Problem Language Result Execution time Memory
518328 2022-01-23T11:59:30 Z lucri XOR Sum (info1cup17_xorsum) C++17
100 / 100
 810 ms 17848 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 412 KB Output is correct
2 Correct 3 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 16700 KB Output is correct
2 Correct 430 ms 16784 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 16700 KB Output is correct
2 Correct 430 ms 16784 KB Output is correct
3 Correct 573 ms 17848 KB Output is correct
4 Correct 582 ms 17300 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 412 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 79 ms 2880 KB Output is correct
4 Correct 82 ms 2728 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 412 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 453 ms 16700 KB Output is correct
4 Correct 430 ms 16784 KB Output is correct
5 Correct 573 ms 17848 KB Output is correct
6 Correct 582 ms 17300 KB Output is correct
7 Correct 79 ms 2880 KB Output is correct
8 Correct 82 ms 2728 KB Output is correct
9 Correct 776 ms 17772 KB Output is correct
10 Correct 810 ms 17476 KB Output is correct
11 Correct 808 ms 17592 KB Output is correct