Cod sursa(job #581311)

Utilizator drywaterLazar Vlad drywater Data 13 aprilie 2011 23:39:44
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int n,solx,soly,i,x[100101],q,sol=-1;
struct Trie
{
    Trie *fiu[2];
    int poz;
    Trie()
    {
        fiu[0]=fiu[1]=0;
        poz=0;
    }
};
Trie *t=new Trie;
void ins(Trie *nod,int val,int bit)
{
    if (bit==-1)
    {
        nod->poz=i;
        return ;
    }
    int x=(((1<<bit)&val)>>bit);
    if (nod->fiu[x]==0) nod->fiu[x]=new Trie;
    bit--;
    ins(nod->fiu[x],val,bit);
}
void caut(int val,int bit)
{
    Trie *R=t;
    while (bit!=-1)
    {
        int x=((val&(1<<bit))>>bit);
        if (R->fiu[x^1]) R=R->fiu[x^1];
        else R=R->fiu[x];
        bit-=1;
    }
    if (sol<val^x[R->poz])
    {
        sol=val^x[R->poz];
        solx=(R->poz)+1;
        soly=i;
    }

}
int main(void)
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    ins(t,0,24);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&q);
        x[i]=x[i-1]^q;
        caut(x[i],24);
        ins(t,x[i],24);

    }
    printf("%d %d %d\n",sol,solx,soly);
    return 0;
}