Cod sursa(job #2742514)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 21 aprilie 2021 08:46:00
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define NMAX 100000
#define INF 2e9
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int N,x,v[NMAX+5];
struct Trie
{
    Trie *fiu[2];
    int index;
    Trie()
    {
        index=-1;
        fiu[0]=fiu[1]=NULL;
    }
};
Trie *T=new Trie;
void ins(Trie *nod,int bit,int index)
{
    int bit2=0;
    if(bit==-1)
    {
        nod->index=index;
        return;
    }
    if(((1<<bit)&v[index])!=0)
    {
        bit2=1;
    }
    if(nod->fiu[bit2]==NULL)
    {
        nod->fiu[bit2]=new Trie();
    }
    ins(nod->fiu[bit2],bit-1,index);
}
int query(Trie *nod,int bit,int index)
{
    if(bit==-1)
    {
        return nod->index;
    }
    int bit2=0;
    if(((1<<bit)&v[index])!=0)
    {
        bit2=1;
    }
    if(nod->fiu[1-bit2]!=NULL)
    {
        return query(nod->fiu[1-bit2],bit-1,index);
    }

    return query(nod->fiu[bit2],bit-1,index);


}
int main()
{
    f>>N;
    int vmax=0,start,fin;
    ins(T,20,0);
    for(int i=1; i<=N; i++)
    {
        f>>x;
        v[i]=v[i-1]^x;
        int poz=query(T,20,i);
       // if(i==4) cout<<poz<<" ";
        if((v[poz]^v[i])>vmax)
        {
            vmax=v[i]^v[poz];
            start=poz+1;
            fin=i;

        }
        ins(T,20,i);

    }
    g<<vmax<<" "<<start<<" "<<fin;






}