Cod sursa(job #2123849)

Utilizator boboomBoomerang boboom Data 6 februarie 2018 17:57:12
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 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 nr,int poz)
{
    if(put==-1)
    {
        nod->nr=poz;
        return;
    }
    bool bit_cur=(nr&(1<<put));
    if(nod->fiu[bit_cur]==NULL)
        nod->fiu[bit_cur]=new trie;
    adauga(nod->fiu[bit_cur],put-1,nr,poz);
}

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

int main()
{
    int n;
    fin>>n;
    int maxim=-1;
    int start=0;
    int stop=0;
    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;
}