Cod sursa(job #2123853)

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

long long v[100002];

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

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=0;
    int start;
    int stop;
    adauga(t,21,0,0);
    for(int i=1;i<=n;i++)
    {
        int nr;
        fin>>nr;
        v[i]=v[i-1]^nr;
        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;
}