Cod sursa(job #2276788)

Utilizator 12222Fendt 1000 Vario 12222 Data 5 noiembrie 2018 12:58:20
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax=1e5+2;

int n;
int a[Nmax];

struct Nod
{
   int poz;
   Nod *leg[2];

}*L;

void Add(Nod *p,int x,int poz,int nrbit)
{
    if(nrbit<0)
    {
        p->poz=poz;
        return ;
    }

    bool bit=(x & (1<<nrbit));

    if(p->leg[bit]==0)
    {
        p->leg[bit]=new Nod;
        p->leg[bit]->poz=0;
        p->leg[bit]->leg[0]=p->leg[bit]->leg[1]=0;
    }

    Add(p->leg[bit],x,poz,nrbit-1);
}

int Find(Nod *p,int x,int nrbit)
{
    if(nrbit<0)return p->poz;

    bool bit=(x & (1<<nrbit));

    if(p->leg[1-bit]!=0)return Find(p->leg[1-bit],x,nrbit-1);
    return Find(p->leg[bit],x,nrbit-1);
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
        a[i]^=a[i-1];
    }

    L=new Nod;
    L->poz=0;
    L->leg[0]=L->leg[1]=0;

    int p,sol,st,dr;
    sol=-1;
    st=dr=0;
    Add(L,0,0,22);
    for(int i=1;i<=n;i++)
    {
        p=Find(L,a[i],22);
        if((a[i]^a[p])>sol)
        {
            sol=a[i]^a[p];
            dr=i;
            st=p+1;
        }

        Add(L,a[i],i,22);
    }

    fout<<sol<<" "<<st<<" "<<dr<<"\n";

    fin.close();
    fout.close();
    return 0;
}