Cod sursa(job #2886005)

Utilizator beingsebiPopa Sebastian beingsebi Data 6 aprilie 2022 21:06:55
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 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 = -1, 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;
    static bool r;
    for (int i = 20; 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;
    static bool r;
    for (int i = 20; i >= 0; i--)
    {
        r = x & (1 << i);
        r ^= 1;
        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);
}