Pagini recente » Cod sursa (job #670009) | Cod sursa (job #1011345) | Cod sursa (job #642149) | Cod sursa (job #1860019) | Cod sursa (job #766272)
Cod sursa(job #766272)
#include <cstdio>
#include <algorithm>
using namespace std;
struct trie {
trie *left;
trie *right;
int index;
};
trie *radacina = new trie;
const int N = 100005;
const int nrb = 21;
int n, a, xorp, maxsol, ind, ind2, SOL;
void add(int x, int id)
{
trie *p = radacina;
for(int i = nrb - 1; i >= 0; --i) {
if(((x >> i) & 1) == 0) {
if(p->left == NULL) {
p->left = new trie;
}
p = p->left;
}
else {
if(p->right == NULL)
p->right = new trie;
p = p->right;
}
}
p->index = id;
}
int cauta(int x)
{
int sol = 0;
trie *p = radacina;
for(int i = nrb - 1; i >= 0; --i) {
if(((x >> i) & 1) == 1) {
if(p->left != NULL) {
p = p->left;
sol += 1 << i;
}
else p = p->right;
}
else {
if(p->right != NULL) {
p = p->right;
sol += 1 << i;
}
else p = p->left;
}
}
if(sol > SOL)
ind = p->index;
return sol;
}
int main()
{
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
scanf("%d", &n);
add(0, 0);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a);
xorp ^= a;
SOL = cauta(xorp);
if(SOL > maxsol) {
maxsol = SOL;
ind2 = i;
}
add(xorp, i);
}
printf("%d %d %d\n", maxsol, ind, ind2);
return 0;
}