Pagini recente » Cod sursa (job #861622) | Cod sursa (job #1389597) | Cod sursa (job #922710) | Cod sursa (job #535489) | Cod sursa (job #2911988)
#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;
}