Cod sursa(job #2026371)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 24 septembrie 2017 13:07:59
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>

using namespace std;

int n,st,dr,rasp,sp[100011];

struct trie
{
    trie *z,*u;
    int who;
    trie ()
    {
        z=NULL;
        u=NULL;
    }
}*nod;
trie*insert (int i, int bit ,trie*nod)
{
    if (nod==NULL)
    {
        nod = new trie;
    }
    if (bit==-1)// am terminat toti biti
    {
        nod->who=i;
        return nod;
    }
    int fin=sp[i]&(1<<bit);
    if (fin==0)
    {
        nod->z=insert(i,bit-1,nod->z);
    }
    else
    {
        nod->u=insert(i,bit-1,nod->u);
    }
}

int find (int val , int bit , trie *nod)
{
    if (bit==-1)
    {
        return nod->who;
    }
    int fin=val&(1<<bit);//fin==0 sau 2
    if (fin==0)
    {
        if (nod->u!=NULL)
        {
            return find(val,bit-1,nod->u);
        }
        else
        {
            return find(val,bit-1,nod->z);
        }
    }
    else
    {
        if (nod->z!=NULL)
        {
            return find (val,bit-1,nod->z);
        }
        else
        {
            return find (val,bit-1,nod->u);
        }
    }
}

int main()
{
    ifstream fin ("xormax.in");
    ofstream fout ("xormax.out");
    fin>>n;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        fin>>x;
        sp[i]=sp[i-1]^x;
    }
    nod=insert(0,21,nod);
    for (int i=1;i<=n;++i)
    {
        int gasit=find(sp[i],21,nod);
        if ((gasit^sp[i])>rasp)
        {
            rasp=gasit^sp[i];
            dr=i;
            st=gasit+1;
        }
        nod=insert(i,21,nod);
    }
    fout<<rasp<<" "<<st<<" "<<dr;
}