Cod sursa(job #2318863)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 13 ianuarie 2019 16:23:47
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

int n,i,x,last,k=1,ke[1000010],son[1000010][2];
bitset<30> a;
pair<int,pair<int,int> > ans;

void upd(int val,int exx)
{
    a.reset();
    int cnt=-1;
    while(val)
    {
        a[++cnt]=val&1;
        val>>=1;
    }
    int poz=1;
    for(int i=21;i>=0;i--)
    {
        if(!son[poz][a[i]])
            son[poz][a[i]]=++k;
        poz=son[poz][a[i]];
    }
    ke[poz]=exx;
}

pair<int,int> getmax(int val)
{
    int poz=1,ret=0;
    for(int i=21;i>=0;i--)
        if(val&(1<<i))
            if(son[poz][0])
                poz=son[poz][0];
            else
                poz=son[poz][1],ret|=(1<<i);
        else
            if(son[poz][1])
                poz=son[poz][1],ret|=(1<<i);
            else
                poz=son[poz][0];
    //cout<<ke[poz]<<' '<<i<<'\n';
    return {ret^val,ke[poz]};
}

int main()
{
    f>>n;
    upd(0,0);
    for(i=1;i<=n;i++)
    {
        f>>x;last^=x;
        pair<int,int> aux=getmax(last);
        ans=max(ans,{aux.first,{-i,aux.second+1}});
        upd(last,i);
    }
    g<<ans.first<<' '<<ans.second.second<<' '<<-ans.second.first;

//    g<<'\n';
//    for(i=1;i<=k;i++)
//    {
//        g<<i<<' '<<son[i][0]<<':'<<son[i][1]<<' '<<ke[i]<<'\n';
//    }
    return 0;
}