Cod sursa(job #198097)

Utilizator CezarMocanCezar Mocan CezarMocan Data 8 iulie 2008 14:55:25
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <cstdio>
#include <cstring>

using namespace std;

long n,i,j,v[100100], x[100100], tr[4100000][2],cf,mx,nrt,t[4100000],start,stop,rez;

inline long min(long a, long b)
    {
    if (a<b)
        return a;
    return b;    
    }

inline long max(long a, long b)
    {
    if (a>b)
        return a;
    return b;    
    }


void add_trie(long p, long poz)
    {
    long b[24],nr=0,aux,curr,cp=p,i;
    memset(b,0,sizeof(b));
    while (p)
        {
        nr++;
        b[nr]=p&1;
        p=p>>1;
        }    
    for (i=1;i<=cf/2;i++)
        {
        aux=b[i];
        b[i]=b[cf-i+1];
        b[cf-i+1]=aux;    
        }
    curr=1;
    for (i=1;i<=cf;i++)
        {
        if (tr[curr][b[i]]==0)
            {
            nrt++;
            tr[curr][b[i]]=nrt;
            }
        curr=tr[curr][b[i]];   
        }   
    if (t[curr]==0||x[t[curr]]>cp)
        t[curr]=poz;     
    }
    
void cauta_trie(long p, long poz)
    {
    long b[24],nr=0,aux,curr,cp=p,i,str,stp;
    memset(b,0,sizeof(b));
    while (p)
        {
        nr++;
        b[nr]=p&1;
        p=p>>1;
        }    
    for (i=1;i<=cf/2;i++)
        {
        aux=b[i];
        b[i]=b[cf-i+1];
        b[cf-i+1]=aux;    
        }
    curr=1;
    for (i=1;i<=cf;i++)
        {
        if (tr[curr][1-b[i]]==0)
            curr=tr[curr][b[i]];   
        else
            curr=tr[curr][1-b[i]];
        }   
    if (t[curr]!=0)
        {
        str=min(poz,t[curr]);
        stp=max(poz,t[curr]);
        if (x[poz]^x[t[curr]]==rez)
            if (stp<stop||(stp==stop&&str>start))
                {
                rez=x[poz]^x[t[curr]];
                start=str;
                stop=stp;    
                }
        if ((x[poz]^x[t[curr]])>rez)  
            {
            rez=x[poz]^x[t[curr]];
            start=str;
            stop=stp;    
            }        
        }
    }

int main(){
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
    scanf("%d",&v[i]);
x[1]=v[1];
for (i=2;i<=n;i++)
    x[i]=x[i-1]^v[i];
for (i=1;i<=n;i++)      
    if (x[i]>mx)
        mx=x[i];
cf=0;
while ((1<<cf)<=mx)
    cf++;
nrt=1;
for (i=1;i<=n;i++)
    add_trie(x[i],i);
for (i=1;i<=n;i++)
    cauta_trie(x[i],i);
printf("%d %d %d\n",rez,start+1,stop);
return 0;    
}