Cod sursa(job #1661172)

Utilizator vancea.catalincatalin vancea.catalin Data 23 martie 2016 17:50:27
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<iostream>
#include<fstream>
#define DX 100010
#define BIT 21
using namespace std;
fstream fin("xormax.in",ios::in),fout("xormax.out",ios::out);
int x[DX];
struct trie
{
    int cine;
    trie *nxt[2];
    trie()
    {
        cine=0;
        nxt[0]=nxt[1]=0;
    }
};
void insert(trie* nod,int put,int nr,int deacuie)
{
    bool bit=nr&(1<<put);
    if(put==-1)
    {
        nod->cine=deacuie;
        return ;
    }
    if(nod->nxt[bit]==NULL) nod->nxt[bit]=new trie;
    insert(nod->nxt[bit],put-1,nr,deacuie);
}
int search(trie* nod,int put,int nr)
{
    bool bit=nr&(1<<put);
    if(put==-1) return nod->cine;
    if(nod->nxt[!bit]==NULL)
        return search(nod->nxt[bit],put-1,nr);
    else
        return search(nod->nxt[!bit],put-1,nr);
}
int main()
{
    int i,n,a,poz,b,l,start=1,stop=1,maxim=-9;
    trie* t=new trie;
    fin>>n;
    insert(t,BIT,0,0);
    for(i=1;i<=n;i++)
    {
        fin>>a;
        x[i]=x[i-1]^a;
        poz=search(t,BIT,x[i]);
        b=x[i]^x[poz];
        l=i-poz+1;
        if(maxim<b )
        {
            maxim=b;
            stop=i;
            start=poz+1;
        }
        insert(t,BIT,x[i],i);
    }
    fout<<maxim<<" "<<start<<" "<<stop<<"\n";
}