Cod sursa(job #2912140)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 6 iulie 2022 22:36:30
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 kb
    
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#define NMAX 100005
 
using std::pair;
 
struct trie {
    int index;
    trie *next[2];
};
 
int xp[NMAX];
 
void swap(int *p, int *q)
{
    int aux = *p;
    *p = *q;
    *q = aux;
}

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

    aux->index = index;
}
 
pair <int, int> search(trie *node1, trie *node2)
{
    if (node1->next[0] && node1->next[1] && node2->next[0] && node2->next[1]) {

        pair<int, int> ans1 = search(node1->next[0], node2->next[1]);
        pair<int, int> ans2 = search(node1->next[1], node2->next[0]);

        if ((xp[ans1.first] ^ xp[ans1.second]) >= (xp[ans2.first] ^ xp[ans2.second])) {

            return ans1;

        } else {

            return ans2;

        }

    } else if (node1->next[0] && node2->next[1]) {

        return search(node1->next[0], node2->next[1]);

    } else if (node1->next[1] && node2->next[0]) {

        return search(node1->next[1], node2->next[0]);

    } else if (node1->next[0] && node2->next[0]) {

        return search(node1->next[0], node2->next[0]);

    } else if (node1->next[1] && node2->next[1]) {

        return search(node1->next[1], node2->next[1]);

    }

    return {node1->index, node2->index};
}
 
int main()
{
    // freopen("xormax.in", "r", stdin);
    // freopen("xormax.out", "w", stdout);
 
    int n;
    scanf("%d", &n);
 
    for (register int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        xp[i] = xp[i - 1] ^ x;
    }
 
    trie *root;
    root = (trie *) calloc(1, sizeof(trie));
    for (register int i = 0; i <= n; ++i)
        add_trie(root, xp[i], i);
 
    pair <int, int> values = search(root, root);

    if (values.first > values.second)
        swap(&values.first, &values.second);

    int l = values.first + 1;
    int r = values.second;

    printf("%d %d %d\n", (xp[r] ^ xp[l - 1]), l, r);
    return 0;
}