Cod sursa(job #2329713)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 27 ianuarie 2019 12:35:40
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("xormax.in");
ofstream g ("xormax.out");
const int nmax=1e5+3;
int n,ans,ba,ndt,act,st,dr,a,v[nmax],usu[1<<21],nd[1<<21][2];
void update(int nr,int poz)
{
    int a,b;
    for(a=0,b=(1<<20);b;b>>=1)
    {
        ba=((nr|b)==nr);
        if(nd[a][ba]) a=nd[a][ba];
        else
        {
            ++ndt;
            nd[a][ba]=ndt;
            a=ndt;
        }
    }
    usu[a]=poz;
}
int query(int nr)
{
    int a,b;
    for(a=0,b=(1<<20);b;b>>=1)
    {
        ba=((nr|b)==nr);
        if(nd[a][!ba]) a=nd[a][!ba];
        else a=nd[a][ba];
    }
    return usu[a];
}
int main()
{
    f>>n;
    update(0,0);
    ans=-1;
    for(int i=1;i<=n;++i)
    {
        f>>a;
        v[i]=v[i-1]^a;
        act=query(v[i]);
        if((v[i]^v[act])>ans)
        {
            ans=v[i]^v[act];
            st=act+1;
            dr=i;
        }
        update(v[i],i);
    }
    g<<ans<<' '<<st<<' '<<dr;
    return 0;
}