Cod sursa(job #2965054)

Utilizator CristeaCristianCristea Cristian CristeaCristian Data 14 ianuarie 2023 12:52:00
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>

using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int SIGMA = 2;
struct Trie
{
    int pos;
    Trie* children[SIGMA];

    Trie()
    {
        pos = -1;
        for(int i = 0; i < SIGMA; i++)
            children[i] = NULL;
    }
};
Trie* trie = new Trie();
void insert(Trie* root, int x, int pos, int bit = 21)
{
    if(bit == -1)
    {
        root->pos = pos;
        return;
    }
    int nxt = ((x & (1 << bit)) != 0);
    if(root->children[nxt] == NULL)
        root->children[nxt] = new Trie();
    insert(root->children[nxt], x, pos, bit - 1);
}

pair<int, int> query(Trie* root, int x, int bit = 21, int ans = 0)
{
    if(bit == -1)
        return {ans, root->pos};
    int nxt = ((x & (1 << bit)) == 0);
    if(root->children[nxt] == NULL)
        nxt = nxt ^ 1;
    return query(root->children[nxt], x, bit - 1, ans + (1 << bit) * nxt);
}
int main()
{
    int n, i, j, ans = -1, l, r, xr = 0, x;
    cin >> n;
    insert(trie, 0, 0);
    for(i = 1; i <= n; i++)
    {
        cin >> x;
        xr ^= x;
        pair<int, int> p = query(trie, xr);
        p.first ^= xr;
        if(p.first > ans)
        {
            ans = p.first;
            l = p.second + 1;
            r = i;
        }
        insert(trie, xr, i);
    }
    cout << ans << ' ' << l << ' ' << r;
    return 0;
}