Cod sursa(job #2225261)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 26 iulie 2018 14:47:10
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 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;

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=cap;
    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];
        }
        else
        {
            if (A->urm[0]==NULL)
                A->urm[0]=new NOD;
            A=A->urm[0];
        }
        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]);
        cop=sum[i];
        X=0;
        poz=-1;
        A=cap;
        for (j=20; j>=0; j--)
        {
            if (cop>=P[j])
            {
                K=1;
                cop-=P[j];
            }
            else
                K=0;
            if (A->urm[1-K]!=NULL)
            {
                X+=P[j];
                A=A->urm[1-K];
            }
            else
                A=A->urm[K];
        }
        if (ANS<X)
        {
            ANS=X;
            en=i;
            be=A->V+1;
        }
    }
    fout << ANS << " " << be << " " << en << '\n';
    fin.close();
    fout.close();
    return 0;
}