Cod sursa(job #819798)

Utilizator geniucosOncescu Costin geniucos Data 19 noiembrie 2012 18:32:23
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<cstdio>
#include<cstring>
using namespace std;
int maxi,val,c,n,in,sf,st,dr,i,j,s[23],a[100005];
struct nod
{
    int obt;
    nod *urm[1];
    nod()
    {
        obt=0;
        memset(urm,0,sizeof(urm));
    }
};
nod *t,*p,*q;
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
t=new nod;
maxi=-1;
for(i=1;i<=n;i++)
{
    c=(c^a[i]);
    for(j=0;j<=20;j++)
    {
        if(c&(1<<j)) s[21-j]=1;
        else s[21-j]=0;
    }
    ///////////////////////////////////////////push
    p=t;
    for(j=1;j<=21;j++)
    {
        if(p->urm[s[j]]==0)
        {
            q=new nod;
            p->urm[s[j]]=q;
            p=q;
        }
        else p=p->urm[s[j]];
        if(j==21) p->obt=i;
    }
    ///////////////////////////////////////////query
    val=0;
    p=t;
    for(j=1;j<=21;j++)
    {
        s[j]=1-s[j];
        if(p->urm[s[j]]!=0)
        {
            val=val+(1<<(21-j));
            p=p->urm[s[j]];
        }
        else p=p->urm[1-s[j]];
    }
    in=(p->obt)+1;
    sf=i;
    ///////////////////////////////////////////prelucrare informatii
    if(val>maxi)
    {
        maxi=val;
        st=in;
        dr=sf;
    }
}
if(maxi!=-1) printf("%d %d %d\n",maxi,st,dr);
else printf("0 1 1\n");
return 0;
}