Cod sursa(job #1253733)

Utilizator acomAndrei Comaneci acom Data 1 noiembrie 2014 18:53:11
Problema Xor Max Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<cstdio>
using namespace std;
#define NMAX 100005
struct trie
{
    int nr;
    trie *f[2];
    trie()
    {
        nr=0;
        f[0]=f[1]=0;
    }
} *root;
int n,x,s,t,poz,smax,pmax,umax,a[NMAX],P[1<<21];
void adauga(int x, trie *r, int nr, int poz)
{
    if (nr)
    {
        int y=x&(1<<nr),z=0;
        if (y) z=1;
        if (!r->f[z])
            r->f[z]=new trie;
        adauga(x^y,r->f[z],nr-1,poz);
    }
    else
        r->nr=poz;
}
int cauta(int x, trie *r, int nr)
{
    if (nr)
    {
        int y=x&(1<<nr),z=0;
        if (y) z=1;
        if (r->f[1-z])
            return cauta(x^y,r->f[1-z],nr-1);
        else
            return cauta(x^y,r->f[z],nr-1);
    }
    else
        return r->nr;
}
int main()
{
    int i;
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    for (i=2,P[0]=P[1]=1;i<(1<<21);++i)
        P[i]=1+P[i>>1];
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&x);
        a[i]=a[i-1]^x;
        if (t<P[a[i]])
            t=P[a[i]];
    }
    root=new trie;
    adauga(0,root,--t,0);
    for (i=1;i<=n;++i)
    {
        poz=cauta(a[i],root,t);
        s=a[i]^a[poz];
        if (s<=a[i] && smax<a[i])
            smax=a[i], pmax=umax=i;
        if (s>smax)
            smax=s, pmax=poz+1, umax=i;
        adauga(a[i],root,t,i);
    }
    printf("%d %d %d\n",smax,pmax,umax);
    return 0;
}