Cod sursa(job #788980)

Utilizator round2Test P round2 Data 16 septembrie 2012 13:33:01
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Max 100001

struct trie{
    struct trie*f[2];
    int p;
    trie(){ memset(f,0,sizeof(f)); p=0; } }*t;

int n,x[Max],xmax,p,p1,u;

void add(int x,int p)
{
    trie *g=t;
    int urm;
    for(int i=20;i>=0;i--)
    {
        if(x&(1<<i))urm=1; else urm=0;
        if(g->f[urm]==0)g->f[urm]=new trie;
        g=g->f[urm];
    }
        g->p=p;
}

int find(int x)
{
    trie *g=t;
    int urm;
    for(int i=20;i>=0;i--)
    {
        if(x&(1<<i))urm=0; else urm=1;
        if(g->f[urm]==0)urm=!urm;
        g=g->f[urm];
    }
        return g->p;
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x[i]);
            x[i]^=x[i-1];
        }
        t=new trie;
        add(x[1],1);
        xmax=x[1]; p=u=1;
        for(int i=2;i<=n;i++)
        {
            p1=find(x[i]);
            if((x[p1]^x[i])>xmax){p=p1+1;u=i;xmax=x[p1]^x[i];}
            add(x[i],i);
        }
    printf("%d %d %d\n",xmax,p,u);

    return 0;
}