Cod sursa(job #3242387)

Utilizator Mihai_999Diaconeasa Mihai Mihai_999 Data 11 septembrie 2024 19:24:01
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
#define nl '\n'

using namespace std;

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

const int NMAX = 1e5+5;

int n, v[NMAX];

struct node
{
    int type, val, ind;
    node *nx[2];
    node()
    {
        nx[0] = nx[1] = NULL;
        type = -1;
        val = 0;
        ind = -1;
    }
};
node *root, *crt, *gett;

void baga(int val, int ind)
{
    crt = root;
    for (int i = 20; i >= 0; i--)
    {
        int bit = ((val & (1<<i)))>>i;
        if (crt->nx[bit] == NULL)
        {
            crt->nx[bit] = new node;
            crt->nx[bit]->type = bit;
        }
        crt = crt->nx[bit];
    }
    crt->val = val;
    crt->ind = ind;
    return;
}

node *cauta(int val)
{
    crt = root;
    for (int i = 20; i >= 0; i--)
    {
        int bit = (val & (1<<i))>>i;
        if (crt->nx[1-bit] != NULL)
            crt = crt->nx[1-bit];
        else
            crt = crt->nx[bit];
    }
    return crt;
}

int main()
{
    int aux = 0, maxi = 0, low = -1, high = -1;
    root = new node;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    for (int i = 1; i <= n; i++)
    {
        baga(aux, i-1);
        aux ^= v[i];
        gett = cauta(aux);
        int crtAns = aux ^ (gett->val);
        if (crtAns > maxi)
        {
            maxi = crtAns;
            low = gett->ind+1;
            high = i;
        }
    }
    fout << maxi << ' ' << low << ' ' << high;
    return 0;
}