Cod sursa(job #2225212)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 26 iulie 2018 13:20:26
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 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[2];

int N, i, j, nr, en, be;
int P[BITS], sum[VAL], ANS;
bool ok;

void ADD_IN_TRIE(int cop)
{
    A[0]=cap;
    for (j=20; j>=0; j--)
    {
        ok=false;
        if (cop>=P[j])
        {
            cop-=P[j];
            if (A[0]->urm[1]==NULL)
                A[0]->urm[1]=new NOD, ok=true;
            A[0]=A[0]->urm[1];
        }
        else
        {
            if (A[0]->urm[0]==NULL)
                A[0]->urm[0]=new NOD, ok=true;
            A[0]=A[0]->urm[0];
        }
        if (ok==true)
            A[0]->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);
    for (i=1; i<=N; i++)
    {
        fin >> nr;
        sum[i]=sum[i-1] ^ nr;
        ADD_IN_TRIE(sum[i]);
    }
    A[0]=A[1]=cap;
    for (i=20; i>=0; i--)
    {
        nr=0;
        for (j=0; j<2; j++)
        {
            if (A[0]->urm[j]!=NULL)
                nr++;
            if (A[1]->urm[j]!=NULL)
                nr++;
        }
        if (nr==4)
        {
            if (max(A[0]->urm[0]->V, A[1]->urm[1]->V)<max(A[0]->urm[1]->V, A[1]->urm[0]->V))
            {
                A[0]=A[0]->urm[0];
                A[1]=A[1]->urm[1];
            }
            else
            {
                A[0]=A[0]->urm[1];
                A[1]=A[1]->urm[0];
            }
            continue;
        }
        for (j=0; j<=1; j++)
        {
            if (A[0]->urm[j]==NULL)
            {
                A[0]=A[0]->urm[1-j];
                if (A[1]->urm[j]!=NULL)
                    A[1]=A[1]->urm[j];
                else
                    A[1]=A[1]->urm[1-j];
                break;
            }
            if (A[1]->urm[j]==NULL)
            {
                A[1]=A[1]->urm[1-j];
                if (A[0]->urm[j]!=NULL)
                    A[0]=A[0]->urm[j];
                else
                    A[0]=A[0]->urm[1-j];
                break;
            }
        }
    }
    be=min(A[0]->V, A[1]->V)+1;
    en=max(A[0]->V, A[1]->V);
    ANS=(sum[be] ^ sum[en]);
    if (ANS==0)
        en=1;
    for (j=en; j>=be; j--)
    {
        if ((sum[en] ^ sum[j])==ANS)
        {
            be=j;
            break;
        }
    }
    fout << ANS << " " << be << " " << en << '\n';
    fin.close();
    fout.close();
    return 0;
}