Cod sursa(job #3335257)

Utilizator rapidu36Victor Manz rapidu36 Data 22 ianuarie 2026 09:35:09
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>

using namespace std;

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()
{
    ifstream in("xormax.in");
    ofstream out("xormax.out");
    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);
        //out << i << ": " << pref << " " << "s = " << s_max_i << " ... poz = " << poz_max_i;
        //out << "\n";
        if (s_max_i > s_max)
        {
            s_max = s_max_i;
            st = poz_max_i + 1;
            dr = i;
        }
        r = adauga(r, pref, i, NB);
    }
    in.close();
    out << s_max << " " << st << " " << dr << "\n";
    out.close();
    return 0;
}