Cod sursa(job #2240964)

Utilizator lil_blocAnonymous Anonymous lil_bloc Data 14 septembrie 2018 15:52:53
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n,i,a,A,rez,c,xr,nr;
int v[100005];
bool b[25];

struct trie
{
    int id;
    trie *f[2];
    trie ()
    {
        id=0;
        f[0]=f[1]=0;
    }
};
trie *T = new trie;

void bag(trie *nd,bool *bl)
{
    if(bl<b)
    {
        nd->id=i;
        return;
    }
    if(nd->f[*bl]==0)
        nd->f[*bl] = new trie;
    bag(nd->f[*bl], bl-1);
}

void calc(trie *nd,bool *bl)
{
    if(bl<b)
    {
        c=nd->id;
        return;
    }
    int y=(*bl==0)?1:0;
    if(nd->f[y]==0)  calc(nd->f[*bl], bl-1);
    else calc(nd->f[y], bl-1);
}

int gest(int x)
{
    int l=19;
    for(int i=l;i>=0;i--)
    {
        if(x&(1<<i))  b[i]=1;
        else    b[i]=0;
    }
    bag(T, b+l);
    calc(T, b+l);
    int r=x^v[c];
    return r;
}

int main() {

    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
        if(v[i]>rez)
        {   rez=v[i];   a=A=i;  }
    }

    rez=0;
    a=1;    A=1;
    for(i=1;i<=n;i++)
    {
        v[i]^=v[i-1];
        nr=gest(v[i]);
        if(nr>rez)
        {
            rez=nr;
            a=c+1;  A=i;
        }
        if(v[i]>rez)
        {   rez=v[i];   a=1;    A=i;    }
    }
    fout<<rez<<"\n";
    fout<<a<<" "<<A<<"\n";
}