Cod sursa(job #2885995)

Utilizator beingsebiPopa Sebastian beingsebi Data 6 aprilie 2022 20:58:59
Problema Xor Max Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
// #define f cin
// #define g cout
struct trie
{
    int lastpoz;
    trie *next[2];
    trie()
    {
        lastpoz = -1;
        next[0] = next[1] = nullptr;
    }
} *root = new trie;
int n, prexor, mxm, le, ri;
void add(int, int);
pair<int, int> getbest(int);
int32_t main()
{
    f >> n;
    add(0, 0);
    for (int i = 1, ax, x; i <= n; i++)
    {
        static pair<int, int> r;
        f >> x;
        prexor ^= x;
        r = getbest(prexor);
        ax = prexor ^ r.first;
        if (ax > mxm)
            mxm = ax, le = r.second, ri = i;
        add(prexor, i);
    }
    g << mxm << " " << le + 1 << " " << ri;
    return 0;
}
void add(int x, int poz)
{
    trie *ax = root;
    for (int i = 20, r; i >= 0; i--)
    {
        r = !!(x & (1 << i));
        if (ax->next[r] == nullptr)
            ax->next[r] = new trie;
        ax = ax->next[r];
    }
    ax->lastpoz = poz;
}
pair<int, int> getbest(int x)
{
    int nr = 0;
    trie *ax = root;
    pair<int, int> rez;
    for (int i = 20, r; i >= 0; i--)
    {
        r = !(!!(x & (1 << i)));
        if (ax->next[r] != nullptr)
            ax = ax->next[r], nr |= r * (1 << i);
        else
            ax = ax->next[!r], nr |= (!r) * (1 << i);
    }
    return make_pair(nr, ax->lastpoz);
}