Cod sursa(job #1012385)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 18 octombrie 2013 21:15:54
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <bitset>

using namespace std;

struct nod
{
    int poz;
    nod *lit[2];
}*root;

int counter;

void create(nod* &unde)
{
    if(unde!=NULL)
        return;
    unde=new nod;
    unde->poz=-1;
    unde->lit[0]=NULL;
    unde->lit[1]=NULL;
}

bitset<25> sir; //de marit

void adauga(nod* &unde,int poz)
{
    if(poz==21)
    {
        if((unde->poz)==-1)
            unde->poz=counter;
        return;
    }
    create(unde->lit[sir[poz]]);
    adauga(unde->lit[sir[poz]],poz+1);
}



inline void convert(int nr)
{
    int i;
    for(i=0;i<21;i++)
    {
        sir[20-i]=(nr&1);
        nr>>=1;
    }
}

int find_max(nod* &unde,int poz)
{
    if(poz==21)
        return unde->poz;
    if(unde->lit[1-sir[poz]]!=NULL)
        return find_max(unde->lit[1-sir[poz]],poz+1);
    return find_max(unde->lit[sir[poz]],poz+1);
}

int main()
{
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");

    int v[100005],n=0,i,t,maxim=-1,start=-1,stop=-1;
    root=NULL;
    create(root);
    convert(0);
    counter=0;
    v[0]=0;
    adauga(root,0);

    counter=1;
    cin>>n;
    for(i=1;i<=n;i++,counter++)
    {
        cin>>v[i];
        v[i]^=v[i-1];
        convert(v[i]);
        adauga(root,0);
        t=find_max(root,0);
        //cout<<"e "<<t<<endl;

        if((v[t]^v[i])>maxim)
        {
            maxim=v[t]^v[i];
            start=t+1;
            stop=i;
        }
        else if((v[t]^v[i])==maxim)
        {
            if((t+1)<start)
            {
                start=t+1;
                stop=i;
            }
        }
    }
    cout<<maxim<<' '<<start<<' '<<stop<<'\n';
    cin.close();
    cout.close();
    return 0;
}