Cod sursa(job #2970337)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 24 ianuarie 2023 22:01:22
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#define int long long

using namespace std;

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

int prefxor, n, x, l, r, rez = -1, mx, pos;

class trie
{
public:
    int ind;
    trie *st, *dr;
    trie () : st(0), dr(0), ind(-1) {}
};

trie *daddy = new trie();

void addmedaddy (trie * root, int p, int x)
{
    if (p == -1)
    {
        root->ind = ++pos;
        return;
    }
    int curr = (x >> p) & 1;
    if (curr)
    {
        if (root->dr == NULL)
            root->dr = new trie();
        addmedaddy(root->dr, p - 1, x);
    }
    else
    {
        if (root->st == NULL)
            root->st = new trie();
        addmedaddy(root->st, p - 1, x);
    }
}

void solve (trie *root, int p, int x)
{
    if (p == -1)
    {
        if (mx > rez)rez = mx, l = root->ind + 1, r = pos + 1;
        return;
    }
    int curr = (x >> p) & 1;
    if (curr)
    {
        if (root->st != NULL)
            mx += (1 << p), solve(root->st, p - 1, x);
        else if (root->dr != NULL)
            solve (root->dr, p - 1, x);
        else
            return;
    }
    else
    {
        if (root->dr != NULL)
            mx += (1 << p), solve(root->dr, p - 1, x);
        else if (root->st != NULL)
            solve (root->st, p - 1, x);
        else
            return;
    }
}

signed main()
{
    for (cin >> n; n-- && cin >> x;)
    {
        prefxor ^= x;
        mx = 0;
        solve(daddy, 20, prefxor);
        addmedaddy (daddy, 20, prefxor);
    }
    cout << rez << ' ' << l << ' ' << r << '\n';
    return 0;
}