Cod sursa(job #1457128)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 2 iulie 2015 18:59:20
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>

using namespace std;

int a[(1<<22)+2],Max,Xor,i,n,uk,v,x,start,stop;

ifstream f("xormax.in");
ofstream g("xormax.out");

inline void det(int nod,int nivel,int x)
{
    if(nivel<0) return;
    if(!nivel) uk=a[nod];
    bool bit=(((x>>nivel)&1)>0);
    int son1=nod<<1, son2=son1+1;

    if(bit)
    {
        if(a[son1]) det(son1,nivel-1,x);
        else v|=(1<<nivel), det(son2,nivel-1,x);
    }
    else
    {
        if(a[son2]) det(son2,nivel-1,x), v|=(1<<nivel);
        else det(son1,nivel-1,x);
    }
}
inline void update(int nod,int nivel,int x)
{
    if(nivel<0) return;

    if(!nivel) a[nod]=i;
    else a[nod]=1;

    bool bit=(((x>>nivel)&1)>0);
    int son1=nod<<1, son2=son1+1;

    if(bit) update(son2,nivel-1,x);
    else  update(son1,nivel-1,x);
}
int main()
{
    f>>n;Max=-1;Xor=0;
    for(i=1;i<=n;++i)
    {
        f>>x;Xor^=x;v=0;
        det(1,20,x);

        if((v^Xor)>Max)  Max=v^Xor,start=uk,stop=i;
        update(1,20,x);
    }
    g<<Max<<" "<<start<<" "<<stop<<'\n';
    return 0;
}