Cod sursa(job #581266)

Utilizator drywaterLazar Vlad drywater Data 13 aprilie 2011 22:44:51
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
int n,b,i,val,x[100001],poz,a,max;
char s[27];
struct Trie{int poz; Trie *bit1; Trie *bit0;
Trie(){poz=-1; bit1=bit0=0;}};
Trie *t=new Trie;
int caut(Trie *nod,char *s)
{
    if (nod->poz>0 || (!nod->bit0 && !nod->bit1)) return nod->poz;
    if ((*s-'0'==0 && nod->bit1) || (*s-'0'==1 && !nod->bit0))
        return caut(nod->bit1,s+1);
    else
        return caut(nod->bit0,s+1);

}
int ins(Trie *nod,char *s)
{
    if (*s=='\0')
    {
        nod->poz=i;
        return 0;
    }
    if (*s=='0')
    {
        if (!nod->bit0) nod->bit0=new Trie;
        ins(nod->bit0,s+1);
        return 0;
    }
    if (!nod->bit1) nod->bit1=new Trie;
        ins(nod->bit1,s+1);
    return 0;
}
int main(void)
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a);
        x[i]=x[i-1]^a;
        a=x[i];
        for (poz=21;poz>=0;poz--)
        {
            s[poz]='0'+a%2;
            a/=2;
        }
        s[22]='\0';
        if (i>1)
        val=caut(t,s);
        ins(t,s);
        if (i>1 && x[i]^x[val]>max)
        {
            max=x[i]^x[val];
            a=val+1;
            b=i;
        }
    }
    printf("%d %d %d\n",max,a,b);
    return 0;
}