Cod sursa(job #2960135)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 3 ianuarie 2023 17:03:56
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <iostream>

using namespace std;

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

#define pii pair <int, int>

const int max_size = 1e5 + 1, sigma = 2, valmax = (1 << 21) - 1;

struct str{
    int poz;
    str * nxt[sigma];
    str()
    {
        poz = 0;
        for (int i = 0; i < sigma; i++)
        {
            nxt[i] = 0;
        }
    }
};

int xp[max_size];
str * t = new str;

void ins (str * nod, int val, int biti, int poz)
{
    if (biti < 0)
    {
        nod -> poz = poz;
        return;
    }
    int urm = (val & (1 << biti));
    if (urm != 0)
    {
        urm = 1;
    }
    if (nod -> nxt[urm] == 0)
    {
        nod -> nxt[urm] = new str;
    }
    ins(nod -> nxt[urm], val,  biti - 1, poz);
}

pii querry (str * nod, int val, int biti, int ans)
{
    if (biti < 0)
    {
        return {ans, nod -> poz};
    }
    int urm = (val & (1 << biti));
    if (urm != 0)
    {
        urm = 1;
    }
    if (nod -> nxt[urm] == 0)
    {
        urm = !urm;
    }
    return querry(nod -> nxt[urm], val, biti - 1, ans + urm * (1 << biti));
}

int main ()
{
    int n, ans = 0, st = 0, dr = 0;
    in >> n;
    ins(t, 0, 21, 0);
    for (int i = 1; i <= n; i++)
    {
        int x;
        in >> x;
        xp[i] = xp[i - 1] ^ x;
        pii aux = querry(t, valmax ^ xp[i], 21, 0);
        if ((aux.first ^ xp[i]) > ans)
        {
            ans = aux.first ^ xp[i];
            st = aux.second + 1;
            dr = i;
        }
        ins(t, xp[i], 21, i);
    }
    out << ans << " " << st << " " << dr;
    in.close();
    out.close();
    return 0;
}