Cod sursa(job #1232180)

Utilizator george_stelianChichirim George george_stelian Data 22 septembrie 2014 12:18:36
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>

using namespace std;

int trie[1<<22],v[100010],n,i,j,sol=-1,st,dr,a,nod;

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d",&n);
    for(i=1;i<(1<<22);i++) trie[i]=-1;
    for(i=1;i<=21;i++) trie[1<<i]=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        v[i]=v[i]^v[i-1];
        for(j=20,nod=1;j>=0;j--)
        {
            if(v[i]&(1<<j)) a=0;
            else a=1;
            if(trie[nod*2+a]>-1) nod=nod*2+a;
            else nod=nod*2+!a;
        }
        j=trie[nod];
        if(sol<(v[i]^v[j]))
        {
            sol=v[i]^v[j];
            st=j+1;
            dr=i;
        }
        for(j=20,nod=1;j>=0;j--)
        {
            if(v[i]&(1<<j)) a=1;
            else a=0;
            nod=nod*2+a;
            trie[nod]=i;
        }
    }
    printf("%d %d %d",sol,st,dr);
    return 0;
}