Cod sursa(job #1163512)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 1 aprilie 2014 13:50:46
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <fstream>

using namespace std;


class nod
{
public:
    nod* unu;
    nod* zero;
    int st;
};

nod radacina;
int macheta;
int icsor[111111];

void update(int x)
{
    macheta^=x;
}

void adauga(int st,int x)
{
    nod *nodCurent;
    nodCurent=&radacina;
    int putere=1<<20;
    while(putere!=0)
    {
        if(((macheta&putere)^(x&putere))==0)
        {
            if(nodCurent->zero==NULL)
            {
                nodCurent->zero=new nod();
            }
            nodCurent=nodCurent->zero;
            putere/=2;
        }
        else
        {
            if(nodCurent->unu==NULL)
            {
                nodCurent->unu=new nod();
            }
            nodCurent=nodCurent->unu;
            putere/=2;
        }
    }
    nodCurent->st=st;
}

int maxim()
{
    nod* nodCurent;
    nodCurent=&radacina;
    int putere=1<<20;
    while(putere!=0)
    {
        if((macheta&putere)==0)
        {
            if(nodCurent->unu!=NULL)
            {
                nodCurent=nodCurent->unu;
                putere/=2;
            }
            else
            {
                nodCurent=nodCurent->zero;
                putere/=2;
            }
        }
        else
        {
            if(nodCurent->zero!=NULL)
            {
                nodCurent=nodCurent->zero;
                putere/=2;
            }
            else
            {
                nodCurent=nodCurent->unu;
                putere/=2;
            }
        }
    }
    return nodCurent->st;
}


int main()
{
    int n,i,a,st,dr,k,rez=-1;
    ifstream in("xormax.in");
    ofstream out("xormax.out");
    in>>n;
    for(i=1;i<=n;++i)
    {
        in>>a;
        icsor[i]=icsor[i-1]^a;
        update(a);
        adauga(i,a);
        k=maxim();
        if((icsor[i]^icsor[k-1])>rez)
        {
            rez=(icsor[i]^icsor[k-1]);
            st=k;
            dr=i;
        }

    }
    out<<rez<<" "<<st<<" "<<dr<<"\n";
    return 0;
}