Cod sursa(job #2559812)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 27 februarie 2020 17:08:38
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>

using namespace std;

int_fast32_t  n,st,dr,rasp,sp[1000011];

struct trie
{
    trie *z,*u;
    int_fast32_t  who;
    trie ()
    {
        z=NULL;
        u=NULL;
    }
}*r;

trie*insertt (int_fast32_t  i, int_fast32_t  bit,trie*nod)
{
    if (nod==NULL)
    {
        nod=new trie;
    }
    if (bit==-1)
    {
        nod->who=i;
        return nod;
    }
    int_fast32_t  fin=sp[i]&(1<<bit);
    if (fin==0)
    {
        nod->z=insertt(i,bit-1,nod->z);
    }
    else
    {
        nod->u=insertt(i,bit-1,nod->u);
    }
    return nod;
}

int_fast32_t  findd (int_fast32_t  val, int_fast32_t  bit, trie *nod)
{
    if (bit==-1)
    {
        return nod->who;
    }
    int_fast32_t  fiin=val&(1<<bit);
    if (fiin==0)
    {
        if (nod->u!=NULL)
        {
            return findd(val,bit-1,nod->u);
        }
        return findd(val,bit-1,nod->z);
    }
    if (nod->z!=NULL)
    {
        return findd(val,bit-1,nod->z);
    }
    return findd(val,bit-1,nod->u);
}

int main()
{
    ios::sync_with_stdio(0);
    ifstream fin ("xormax.in");
    ofstream fout ("xormax.out");
    fin>>n;
    rasp=-1;
    for(int_fast32_t  i=1; i<=n; ++i)
    {
        int_fast32_t  x;
        fin>>x;
        sp[i]=sp[i-1]^x;
    }
    r=insertt(0,21,r);
    for (int_fast32_t  i=1; i<=n; ++i)
    {
        int_fast32_t  gasit=findd(sp[i],21,r);
        if ((sp[gasit]^sp[i])>rasp)
        {
            rasp=sp[gasit]^sp[i];
            dr=i;
            st=gasit+1;
        }
        r=insertt(i,21,r);
    }
    fout<<rasp<<" "<<st<<" "<<dr;
}