Cod sursa(job #2123877)

Utilizator boboomBoomerang boboom Data 6 februarie 2018 18:13:32
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct trie{
    int nr;
    trie *fiu[2];
    trie()
    {
        nr=0;
        fiu[0]=NULL;
        fiu[1]=NULL;
    }
};

trie *t=new trie();

int v[100069];

void adauga(trie *nod,int put,int nr2,int poz)
{
    if(put==-1)
    {
        nod->nr=poz;
        return;
    }
    bool bit_cur=(nr2 & (1<<put));
    if(nod->fiu[bit_cur]==NULL){
        nod->fiu[bit_cur]=new trie();
    }
    adauga(nod->fiu[bit_cur],put-1,nr2,poz);
}

int cauta(trie *nod,int put,int nr2)
{
    if(put==-1)
        return nod->nr;
    bool bit_cur=(nr2 & (1<<put));
    if(nod->fiu[!bit_cur]==NULL)
        return cauta(nod->fiu[bit_cur],put-1,nr2);
    return cauta(nod->fiu[!bit_cur],put-1,nr2);
}

int main()
{
    int n;
    fin>>n;
    int maxim=-1;
    int start;
    int stop;
    adauga(t,21,0,0);
    for(int i=1;i<=n;i++)
    {
        int nr2;
        fin>>nr2;
        v[i]=v[i-1]^nr2;
        int poz=cauta(t,21,v[i]);
        if((v[poz]^v[i])>maxim)
        {
            maxim=v[poz]^v[i];
            start=poz+1;
            stop=i;
        }
        adauga(t,21,v[i],i);
    }
    fout<<maxim<<" "<<start<<" "<<stop ;
    return 0;
}