Cod sursa(job #3335266)

Utilizator Rizi_SanNen Ioana Madlena Rizi_San Data 22 ianuarie 2026 09:48:29
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("xormax.in");
ofstream out("xormax.out");

const int NB = 21;

struct nod {
    int poz_ult;
    nod *fiu_0, *fiu_1;
};

nod* adauga(nod* p, int val, int poz, int nb)
{
    if (p == NULL)
    {
        p=new nod;
        p->fiu_0 = p->fiu_1 = NULL;
    }
    nb--;
    if (nb == -1)
    {
        p->poz_ult = poz;
        return p;
    }
    if ((val & (1<<nb)) == 0)//bitul curent e 0
    {
        p->fiu_0 = adauga(p->fiu_0, val, poz, nb);
    }
    else
    {
        p->fiu_1 = adauga (p->fiu_1, val, poz, nb);
    }
    return p;
}

void interogare(nod* p,int val, int &s_max, int &poz_max, int nb)
{
    if (nb == 0)
    {
        s_max = 0;
        poz_max = p->poz_ult;
        return;
    }
    nb--;
    int p2 = ((1<<nb) & val);
    if (p2 == 0)
    {
        if (p->fiu_1 != NULL)
        {
            interogare(p->fiu_1, val, s_max, poz_max, nb);
            s_max += (1<< nb);
        }
        else
        {
            interogare(p->fiu_0, val, s_max, poz_max, nb);
        }
    }
    else
    {
        if (p->fiu_0 != NULL)
        {
            interogare(p->fiu_0, val, s_max, poz_max, nb);
            s_max += (1<< nb);
        }
        else
        {
            interogare(p->fiu_1, val, s_max, poz_max, nb);
        }
    }
}

int main()
{
    int n;
    in >> n;

    nod *r = adauga (NULL, 0, 0, NB);

    int pref=0, s_max=-1, st=-1, dr=-1;

    for (int i=1;i<=n; i++)
    {
        int x_i;
        in>> x_i;
        pref ^= x_i;
        int s_max_i, poz_max_i;
        interogare(r, pref, s_max_i, poz_max_i, NB);
        if (s_max_i > s_max)
        {
            s_max=s_max_i;
            st=poz_max_i+1;
            dr=i;
        }
        r=adauga(r, pref, i, NB);
    }

    out<<s_max<<" "<<st<<" "<<dr;
    return 0;
}