Cod sursa(job #1476378)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 25 august 2015 02:48:48
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#define LIM 2097152
using namespace std;
struct trie
{
    int child[3];
    int nodsf;
}a[LIM];
int nd=2,n,maxim=-1000,inc,sf,x[100023];
void push(int nr,int sfarsit)
{
    int nod=1;
    for(int i=21;i>=0;i--)
    {
        int fiu=0;
        if(nr&(1<<i)) fiu=1;
        if(a[nod].child[fiu]==0)
        {
            a[nod].child[fiu]=nd;
            nd++;
        }
        nod=a[nod].child[fiu];
    }
    a[nod].nodsf=sfarsit;
}
void gaseste(int nr,int ssf)
{
    int nod=1;
    for(int i=21;i>=0;i--)
    {
        int fiu=1;
        if(nr&(1<<i)) fiu=0;
        if(a[nod].child[fiu]!=0) nod=a[nod].child[fiu];
        else nod=a[nod].child[1-fiu];
    }
    nod=a[nod].nodsf;
    if(maxim<(x[ssf]^x[nod]))
    {
        maxim=(x[ssf]^x[nod]);
        inc=nod+1;
        sf=ssf;
    }
}
int main()
{
    freopen ("xormax.in","r",stdin);
    freopen ("xormax.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=LIM;i++) a[i].nodsf=-1;
    push(0,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
        x[i]=x[i]^x[i-1];
        gaseste(x[i],i);
        push(x[i],i);
    }
    printf("%d %d %d\n",maxim,inc,sf);
}