Pagini recente » Autentificare | Cod sursa (job #182431) | Arhiva de probleme | Cod sursa (job #2280940) | Cod sursa (job #2912140)
#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;
}