Cod sursa(job #1457382)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 3 iulie 2015 12:07:16
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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=(v|(1<<nivel)), det(son2,nivel-1,x);
    }
    else
    {
        if(a[son2]) det(son2,nivel-1,x), v=(v|(1<<nivel));
        else det(son1,nivel-1,x);
    }
}
inline void update(int nod,int nivel,int x)
{
    if(nivel<0) return;
    a[nod]=i;

    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;

    update(1,20,0);

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