Cod sursa(job #1311052)

Utilizator Tudordmdaniel marin Tudordm Data 7 ianuarie 2015 17:43:29
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>

const int NMAX=100001;

int N,M;
int V[NMAX],X[NMAX];
int trie[NMAX*21][2];

void Update_Trie(int x,int poz){

    int i,bit,nod=0;

    for(i=20;i>=0;--i){

        bit=(x&(1<<i))!=0;
        if (!trie[nod][bit])
            trie[nod][bit]=++M;
        nod=trie[nod][bit];
    }

    trie[nod][0]=poz;
}

int main (){

    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

    scanf("%d\n",&N);

    for (int i=1;i<=N;++i){

        scanf("%d ",V+i);
        X[i]=X[i-1]^V[i];
    }

    int i,j,maxim=-1,nod,bit,temp;
    int st,dr,st2,dr2;

    for (i=N;i>=0;--i)
        Update_Trie(X[i],i);

    for (i=0;i<=N;++i){

        nod=temp=0;
        for (j=20;j>=0;--j){

            bit=(X[i]&(1<<j))!=0;
            bit^=1;

            if(trie[nod][bit]>0){

                nod=trie[nod][bit];
                temp+=(1<<j);
            }
            else if(!trie[nod][bit])
                nod=trie[nod][1-bit];
        }
        if(N<10)
            if(trie[nod][0]+1>i)
                continue;
        st2=trie[nod][0];
        dr2=i;
        if(st2+1>dr2)  st2^=dr2,dr2^=st2,st2^=dr2;
        ++st2;

        if(maxim<temp){

            maxim=temp;
            st=st2;
            dr=dr2;
        }
        else if(maxim==temp)
            if(dr>dr2){

                st=st2;
                dr=dr2;
            }
            else if(dr==dr2)
                if(st<st2)
                    st=st2;
    }

    printf("%d %d %d\n",maxim,st,dr);

    return 0;
}