Cod sursa(job #1777069)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 12 octombrie 2016 00:38:47
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <vector>

using namespace std;

struct trie
{
    int poz;
    int v[2];
    trie()
    {
        poz=v[0]=v[1]=0;
    }
};

vector<trie> arb;
int v[100010];

void trie_add(int x,int poz)
{
    int nod=0,p;
    for(int i=21;i>=0;i--)
    {
        if(x&(1<<i)) p=1;
        else p=0;
        if(arb[nod].v[p]==0)
        {
            arb.push_back(trie());
            arb[nod].v[p]=arb.size()-1;
        }
        nod=arb[nod].v[p];
    }
    arb[nod].poz=poz;
}

int trie_find(int x)
{
    int nod=0,p;
    for(int i=21;i>=0;i--)
    {
        if(x&(1<<i)) p=0;
        else p=1;
        if(arb[nod].v[p]==0) p^=1;
        nod=arb[nod].v[p];
    }
    return arb[nod].poz;
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,maxx=-1,i1,j1,poz;
    scanf("%d",&n);
    arb.push_back(trie());
    trie_add(0,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        v[i]=v[i-1]^v[i];
        poz=trie_find(v[i]);
        if(v[i]^v[poz]>maxx) {maxx=v[i]^v[poz];i1=poz+1;j1=i;}
        trie_add(v[i],i);
    }
    printf("%d %d %d",maxx,i1,j1);
    return 0;
}