Cod sursa(job #2236088)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 28 august 2018 08:38:43
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

const int N=100000+5;
int n,itr,kid[N*21][2],AtomicBomb[N*21],cnt=1;
int PrefixXor=0;

inline void add(int x)
{
    int pp=1;
    AtomicBomb[pp]=itr;
    for(int i=20;i>=0;i--)
    {
        int bit;
        if(x&(1<<i))
            bit=1;
        else
            bit=0;
        if(kid[pp][bit]==0)
            kid[pp][bit]=++cnt;
        pp=kid[pp][bit];
        AtomicBomb[pp]=itr;
    }
}

int NeutronBomb;

inline int slove(int x)
{
    int ans=0;
    int pp=1;
    for(int i=20;i>=0;i--)
    {
        int bit;
        if(x&(1<<i))
            bit=1;
        else
            bit=0;
        if(kid[pp][0]==0 && kid[pp][1]==0)
        {
            NeutronBomb=AtomicBomb[pp];
            return ans;
        }
        if(kid[pp][1-bit])
            pp=kid[pp][1-bit],ans+=(1<<i);
        else
            pp=kid[pp][bit];
    }
    NeutronBomb=AtomicBomb[pp];
    return ans;
}

int Answer=-1;
int F,S;

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    cin>>n;
    add(0);
    for(itr=1;itr<=n;itr++)
    {
        int x;
        cin>>x;
        PrefixXor^=x;
        int Cur=slove(PrefixXor);
        if(Cur>Answer)
        {
            Answer=Cur;
            F=NeutronBomb+1;
            S=itr;
        }
        add(PrefixXor);
    }
    cout<<Answer<<" "<<F<<" "<<S<<"\n";
    return 0;
}