Cod sursa(job #2823705)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 29 decembrie 2021 14:31:35
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int maxN = 100'005;
int n, xorp[maxN], ans = -1, st, dr;

struct arbore {
    int ind;
    bool amin;
}arb[4 * (1 << 20)];

void update(int nod, int poz, int depth)
{
    if(depth == -1)
    {
        arb[nod].ind = poz;
        arb[nod].amin = true;
        return;
    }
    if(xorp[poz] & (1 << depth))
        update(2 * nod + 1, poz, depth - 1);
    else
        update(2 * nod, poz, depth - 1);
    arb[nod].amin = arb[2 * nod].amin | arb[2 * nod + 1].amin;
}

int query(int nod, int val, int depth)
{
    if(depth == -1)
        return arb[nod].ind;
    if(((val & (1 << depth)) && arb[2 * nod].amin == true) || arb[2 * nod + 1].amin == false)
        return query(2 * nod, val, depth - 1);
    return query(2 * nod + 1, val, depth - 1);
}

int main()
{
    fin >> n;
    update(1, 0, 20);
    for(int i = 1; i <= n; i++)
    {
        fin >> xorp[i];
        xorp[i] ^= xorp[i - 1];
        int maxi = query(1, xorp[i], 20);
        if(xorp[i] ^ xorp[maxi] > ans)
        {
            ans = xorp[i] ^ xorp[maxi];
            st = maxi + 1;
            dr = i;
        }
        update(1, i, 20);
    }
    fout << ans << ' ' << st << ' ' << dr << '\n';
}