Cod sursa(job #1844019)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 9 ianuarie 2017 17:28:40
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>

using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,i,step,x,st,dr,sol,k,v[1<<17];
struct trie
{
    int ind,S[2];
}T[1<<20];
int main()
{
    f>>n;
    for(i=0;i<21;++i) T[i].S[0]=++k;
    for(i=1;i<=n;++i)
    {
        f>>v[i];
        v[i]^=v[i-1];
        x=0;
        for(step=1<<20;step;step>>=1)
        {
            int bit=((v[i]&step)==0);
            if(!T[x].S[bit]) x=T[x].S[bit^1];
            else x=T[x].S[bit];
        }
        if(sol<v[i]^v[T[x].ind])
        {
            sol=v[i]^v[T[x].ind];
            st=T[x].ind;
            dr=i;
        }
        x=0;
        for(step=1<<20;step;step>>=1)
        {
            int bit=((v[i]&step)>0);
            if(!T[x].S[bit]) T[x].S[bit]=++k;
            x=T[x].S[bit];
        }
        T[x].ind=i;
    }
    g<<sol<<' '<<st+1<<' '<<dr;
    return 0;
}