Cod sursa(job #3264173)

Utilizator tudor_costinCostin Tudor tudor_costin Data 18 decembrie 2024 18:20:05
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int Nmax=1e5+5;
int a[Nmax],last[21*Nmax];
struct trie
{
    trie* l;
    trie* r;
};
void add(int x,int niv,trie* t)
{
    if(niv<0) return;
    if(((1<<niv)&x)!=0)
    {
        ///1 pe niv
        if(t->r==NULL) t->r=new trie();
        add(x,niv-1,t->r);
    }
    else
    {
        ///0 pe niv
        if(t->l==NULL) t->l=new trie();
        add(x,niv-1,t->l);
    }
}
int ans(int x,int niv,trie *t)
{
    if(niv<0) return 0;
    if(((1<<niv)&x)!=0)
    {
        if(t->l!=NULL)
        {
            return ans(x,niv-1,t->l);
        }
        else
        {
            return ans(x,niv-1,t->r)+(1<<niv);
        }
    }
    else
    {
        if(t->r!=NULL)
        {
            return ans(x,niv-1,t->r)+(1<<niv);
        }
        else
        {
            return ans(x,niv-1,t->l);
        }
    }
}
int main()
{
    int n;
    fin>>n;
    int start=0,stop=0,sol=-1;
    trie* t=new trie();
    add(0,21,t);
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
        a[i]=a[i]^a[i-1];
        int x=ans(a[i],21,t);
        ///cout<<x<<' '<<a[i]<<' '<<(x^a[i])<<' '<<last[x]<<'\n';
        if((x^a[i])>sol)
        {
            sol=x^a[i];
            start=last[x]+1;
            stop=i;
        }
        add(a[i],21,t);
        last[a[i]]=i;
    }
    fout<<sol<<' '<<start<<' '<<stop<<'\n';
    return 0;
}