Cod sursa(job #1777086)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 12 octombrie 2016 01:31:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

using namespace std;

int arb[1<<22];
int v[100010];

void add_trie(int x,int poz)
{
    int nod=1,a;
    for(int i=20;i>=0;i--)
    {
        if(x&(1<<i)) a=1;
        else a=0;
        arb[nod*2+a]=poz;
        nod=nod*2+a;
    }
}

int find_trie(int x)
{
    int nod=1,a;
    for(int i=20;i>=0;i--)
    {
        if(x&(1<<i)) a=0;
        else a=1;
        if(arb[nod*2+a]>-1) nod=nod*2+a;
        else nod=nod*2+!a;
    }
    return arb[nod];
}

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