Cod sursa(job #2228244)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 3 august 2018 00:15:27
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <vector>
#define BITS 25
#define VAL 100005

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct NOD
{
    int V;
    NOD *urm[2];
};

NOD *cap=new NOD;
NOD *A=new NOD, *B=new NOD;

int N, i, j, nr, en, be;
int P[BITS], sum[VAL], ANS;
int cop, X, poz, nxtA, nxtB;

void ADD_IN_TRIE(NOD *A, NOD *B, int j)
{
    if (cop>=P[j])
    {
        cop-=P[j];
        if (A->urm[1]==NULL)
            A->urm[1]=new NOD;
        nxtA=1;
    }
    else
    {
        if (A->urm[0]==NULL)
            A->urm[0]=new NOD;
        nxtA=0;
    }
    if (B->urm[1-nxtA]!=NULL)
    {
        X+=P[j];
        nxtB=1-nxtA;
    }
    else
        nxtB=nxtA;
    if (j==0)
    {
        if (ANS<X)
        {
            ANS=X;
            en=i;
            be=B->urm[nxtB]->V+1;
            A->urm[nxtA]->V=i;
        }
        A->urm[nxtA]->V=i;
        return;
    }
    ADD_IN_TRIE(A->urm[nxtA], B->urm[nxtB], j-1);
}

int main()
{
    fin >> N;
    P[0]=1;
    for (i=1; i<=20; i++)
        P[i]=P[i-1]*2;
    ANS=be=en=-1;
    i=0;
    ADD_IN_TRIE(cap, cap, 20);
    for (i=1; i<=N; i++)
    {
        fin >> nr;
        sum[i]=(sum[i-1] ^ nr);
        cop=sum[i];
        X=0;
        ADD_IN_TRIE(cap, cap, 20);
    }
    fout << ANS << " " << be << " " << en << '\n';
    fin.close();
    fout.close();
    return 0;
}