Cod sursa(job #2093717)

Utilizator KonoplyankaKonoplyanka Konoplyanka Data 24 decembrie 2017 13:18:33
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include<cstdio>

#include<algorithm>

#define idx(x) sv[x].second

using std::pair;
using std::make_pair;

int v[100005];
pair<int, int> sv[100005];

int start, stop, ret=-1;

bool isbetter(int nstart, int nstop, int xr)
{
    if(nstop==0)
        return 0;

    if(nstop<=nstart)
        std::swap(nstop, nstart);
    if(stop<=start)
        std::swap(stop, start);

    if(xr > ret)
        return 1;
    if(xr < ret)
        return 0;

    if(nstop<stop)
        return 1;
    if(nstop>stop)
        return 0;

    return nstart > start;
}

void tryupdate(int nstart, int nstop)
{
    if(isbetter(idx(nstart), idx(nstop), v[nstart]^v[nstop]))
        start=idx(nstart), stop=idx(nstop), ret=v[nstart]^v[nstop];
}

void func(int bit, int sa, int ea, int sb, int eb)
{
    if(sa>=eb)
        return;

    if(bit<0){
        for(int i=sa;i<ea;i++)
            tryupdate(i, std::lower_bound(sv+sb, sv+eb, make_pair(v[sb], idx(sa)))-sv);

        for(int i=sb;i<eb;i++)
            tryupdate(i, std::lower_bound(sv+sa, sv+ea, make_pair(v[sa], idx(sb)))-sv);
        return;
    }

    int num=1<<bit;

    int start=sa, end=ea;
    while(start<end){
        int mid=(start+end)/2;
        if(v[mid] & num)
            end=mid;
        else
            start=mid+1;
    }

    int p1=start;

    start=sb,end=eb;
    while(start<end){
        int mid=(start+end)/2;
        if(v[mid] & num)
            end=mid;
        else
            start=mid+1;
    }
    int p2=start;

    bool ok1=p1!=sa && p2!=eb;
    bool ok2=p1!=ea && p2!=sb;
    pair<int, int> p;

    if(ok1)
        func(bit-1,sa,p1,p2,eb);


    if(ok2)
        func(bit-1,p1,ea,sb,p2);

    if(!ok1 && !ok2){
        if(sa!=p1 && sb!=p2)
            func(bit-1,sa,p1,sb,p2);
        if(ea!=p1 && eb!=p2)
            func(bit-1,p1,ea,p2,eb);
    }
}

int main(void)
{
    freopen("xormax.in","r",stdin);
#ifdef INFOARENA
    freopen("xormax.out","w",stdout);
#endif

    int n;
    scanf("%d",&n);
    n++;

    for(int i=1;i<n;i++){
        scanf("%d",v+i);
        v[i]^=v[i-1];
        sv[i]=make_pair(v[i],i);
    }

    stop=1;
    ret=v[1];

    std::sort(sv,sv+n);
    for(int i=0;i<n;i++)
        v[i]=sv[i].first;

    func(21,0,n,0,n);
    if(start > stop)
        std::swap(start, stop);

    printf("%d %d %d\n", ret, start+1, stop);

    return 0;

}