Cod sursa(job #2911988)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 6 iulie 2022 12:56:24
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

struct trie {
    int number;
    trie *next[2];
};

int xp[NMAX];

void add_trie(trie *root, int value)
{
    trie *aux = root;
    for (int bit = 20; bit >= 0; --bit)
        if (value & (1 << bit)) {
            
            if (!aux->next[1])
                aux->next[1] = (trie *) calloc(1, sizeof(trie));
            
            aux->next[1]->number = ((aux->number << 1) ^ 1);
            aux = aux->next[1];

        } else {

            if (!aux->next[0])
                aux->next[0] = (trie *) calloc(1, sizeof(trie));

            aux->next[0]->number = (aux->number << 1);
            aux = aux->next[0];
        }
}

pair <int, int> search(trie *root)
{
    trie *aux1 = root, *aux2 = root;
    for (int bit = 20; bit >= 0; --bit) {
        if (aux1->next[0] && aux2->next[1]) {
            aux1 = aux1->next[0];
            aux2 = aux2->next[1];
        } else if (aux1->next[1] && aux2->next[0]) {
            aux1 = aux1->next[1];
            aux2 = aux2->next[0];
        } else if (aux1->next[0] && aux2->next[0]) {
            aux1 = aux1->next[0];
            aux2 = aux2->next[0];
        } else {
            aux1 = aux1->next[1];
            aux2 = aux2->next[1];
        }
    }

    pair <int, int> res = {aux1->number, aux2->number};
    return res;
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    int n;
    cin >> n;

    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        xp[i] = xp[i - 1] ^ x;
    }

    trie * root;
    root = (trie *) calloc(1, sizeof(trie));
    for (int i = 0; i <= n; ++i)
        add_trie(root, xp[i]);

    pair <int, int> values = search(root);

    int l = -1, r = -1;
    for (int i = 0; i <= n; ++i)
        if (xp[i] == values.first || xp[i] == values.second)
            if (l != -1)
                r = i;
            else
                l = i;

    cout << (xp[r] ^ xp[l]) << ' ' << l + 1<< ' ' << r << '\n';
    return 0;
}