Cod sursa(job #946584)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 4 mai 2013 21:26:43
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
// A[i] = al i-lea element al sirului;
// Construim vectorul X[i] = A[1] ^ A[2] ^ ... ^ A[i];
// Pentru fiecare X[i] de la 1 la n cautam un X[j] (j<i) astfel incat X[i]^X[j] sa fie maxim;
// Mentinem toate valorile X[i] intr-un trie cu bitii numarului.

#include<cstdio>

using namespace std;
const int NMAX = 100005;
int i,n,A[NMAX],X[NMAX],SOL=-1,L,R;

struct Trie
{
    int index;
    Trie *Left,*Right;
    Trie()
    {
        index=0;
        Left=Right=NULL;
    }
};
Trie *Root,*Aux;

void Add(int val,int id)
{
    int i;
    for(Aux=Root,i=21;i>=0;i--)
    {
        if((1<<i)&val) // val are bit pe pozitia i
        {
            if(!Aux->Right) Aux->Right=new Trie;
            Aux=Aux->Right;
        }
        else // val nu are bit pe pozitia i
        {
            if(!Aux->Left) Aux->Left=new Trie;
            Aux=Aux->Left;
        }
    }
    Aux->index=id;
}

void Find_Best(int val,int id)
{
    int rez,indice,i;
    for(Aux=Root,i=21;i>=0;i--)
    {
        if((1<<i)&val) // val are bit pe pozitia i si de aceea cautam o solutie fara bit
        {
            if(Aux->Left) Aux=Aux->Left;
            else Aux=Aux->Right;
        }
        else // val nu are bit pe pozitia i si de aceea cautam o solutie cu bit
        {
            if(Aux->Right) Aux=Aux->Right;
            else Aux=Aux->Left;
        }
    }
    indice=Aux->index;
    rez=X[indice]^X[id];
    if(rez>SOL)
    {
        SOL=rez;
        L=indice+1;
        R=id;
    }
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n); Root=new Trie; Add(0,0);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
        X[i]=X[i-1]^A[i];
        Find_Best(X[i],i);
        Add(X[i],i);
    }
    printf("%d %d %d\n",SOL,L,R);
    return 0;
}