Cod sursa(job #1232157)

Utilizator george_stelianChichirim George george_stelian Data 22 septembrie 2014 11:33:26
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct trie
{
    int urm[2][21],poz;
}v[2100010];
pair<int,int> aux;
int n,i,sol,st,dr,a,x,nr;

void trie_push(int x,int poz)
{
    int i,nod=1,put=1<<20,a;
    for(i=20;i>=0;i--,put>>=1)
    {
        if(x&put) a=1;
        else a=0;
        if(v[nod].urm[a][i]) nod=v[nod].urm[a][i];
        else nod=v[nod].urm[a][i]=++nr;
    }
    v[nod].poz=poz;
}

pair<int,int> trie_query(int x)
{
    int i,nod=1,s=0,put=1<<20,poz,a;
    for(i=20;i>=0;i--,put>>=1)
    {
        if(x&put) a=0;
        else a=1;
        if(v[nod].urm[a][i])
        {
            s|=a*put;
            nod=v[nod].urm[a][i];
        }
        else
        {
            s|=(!a)*put;
            nod=v[nod].urm[!a][i];
        }
    }
    return make_pair(s,v[nod].poz);
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d",&n);
    nr=1;
    trie_push(0,0);
    sol=-1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        a^=x;
        trie_push(a,i);
        aux=trie_query(a);
        if(sol<a^aux.first)
        {
            sol=a^aux.first;
            st=aux.second+1;
            dr=i;

        }
    }
    printf("%d %d %d",sol,st,dr);
    return 0;
}