Cod sursa(job #2229282)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 6 august 2018 14:25:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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, K;

void ADD_IN_TRIE(int cop)
{
    A=B=cap;
    X=0;
    for (j=20; j>=0; j--)
    {
        if (cop>=P[j])
        {
            cop-=P[j];
            if (A->urm[1]==NULL)
                A->urm[1]=new NOD;
            A=A->urm[1];
            K=1;
        }
        else
        {
            if (A->urm[0]==NULL)
                A->urm[0]=new NOD;
            A=A->urm[0];
            K=0;
        }
        if (B->urm[1-K]!=NULL)
        {
            X+=P[j];
            B=B->urm[1-K];
        }
        else
            B=B->urm[K];
        if (j==0 && ANS<X)
        {
            ANS=X;
            en=i;
            be=B->V+1;
        }
        A->V=i;
    }
}

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