Cod sursa(job #2772005)

Utilizator Razvan86Razvan Gabriel Razvan86 Data 30 august 2021 14:05:47
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <bits/stdc++.h>

using namespace std;

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

void numar_binar (int x, int sir[33])
{
    int pozitie_sir=30;
    while (x!=0)
    {
        sir[pozitie_sir] = x%2;
        x = x/2;
        pozitie_sir--;
    }
}

struct nod_arbore
{
    nod_arbore *pointer0;
    nod_arbore *pointer1;
    int valoare;
    int indice;
};

void initializare_nod_arbore_nou (nod_arbore *oarecare)
{
    oarecare->pointer0 = NULL;
    oarecare->pointer1 = NULL;
    oarecare->valoare = 0;
    oarecare->indice = 0;
}

void inserare_arbore (nod_arbore *R, int sir[33])
{
    nod_arbore *parcurgere = R;
    for (int i=0; i<31; i++)
    {
        if (sir[i]==0)
        {
            if ((parcurgere->pointer0)==NULL)
            {
                parcurgere->pointer0 = new nod_arbore;
                parcurgere = parcurgere->pointer0;
                initializare_nod_arbore_nou(parcurgere);
            }
            else
                parcurgere = parcurgere->pointer0;
        }
        else if (sir[i]==1)
        {
            if ((parcurgere->pointer1)==NULL)
            {
                parcurgere->pointer1 = new nod_arbore;
                parcurgere = parcurgere->pointer1;
                initializare_nod_arbore_nou(parcurgere);
            }
            else
                parcurgere = parcurgere->pointer1;
        }
    }
    parcurgere->valoare = sir[31];
    parcurgere->indice = sir[32];
}

void cautare_maxim (nod_arbore *R, int sir[33], int partial, int &maximul, int &initialul, int &finalul)
{
    nod_arbore *parcurgere = R;
    for (int i=0; i<31; i++)
    {
        if (sir[i]==0)
        {
            if ((parcurgere->pointer1)!=NULL)
                parcurgere = parcurgere->pointer1;
            else if ((parcurgere->pointer0)!=NULL)
                parcurgere = parcurgere->pointer0;
            else
                return;
        }
        else if (sir[i]==1)
        {
            if ((parcurgere->pointer0)!=NULL)
                parcurgere = parcurgere->pointer0;
            else if ((parcurgere->pointer1)!=NULL)
                parcurgere = parcurgere->pointer1;
            else
                return;
        }
    }
    if (((parcurgere->valoare)^partial)>=maximul)
    {
        maximul = ((parcurgere->valoare)^partial);
        initialul = parcurgere->indice+1;
        finalul = sir[32];
    }
}

void rsd (nod_arbore *R)
{
    if (R!=NULL)
    {
        cout << R->valoare << " ";
        rsd(R->pointer0);
        rsd(R->pointer1);
    }
}

int main()
{
    int n; int v[100005];
    int partial=0,maximul=0,initialul=0,finalul=0;
    nod_arbore *R = new nod_arbore;
    initializare_nod_arbore_nou(R);
    fin >> n;
    for (int i=1; i<=n; i++)
    {
        fin >> v[i];
        partial = partial^(v[i]);
        int sir[33]={0};
        sir[31] = partial;
        sir[32] = i;
        numar_binar(partial,sir);
        inserare_arbore(R,sir);
        cautare_maxim(R,sir,partial,maximul,initialul,finalul);
    }
    fout << maximul << " " << initialul << " " << finalul;
    return 0;
}