Pagini recente » Monitorul de evaluare | Cod sursa (job #218741) | Cod sursa (job #2094731) | Cod sursa (job #1509119) | Cod sursa (job #766283)
Cod sursa(job #766283)
#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;
}
void cauta(int x, int id)
{
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 > maxsol) {
maxsol = sol;
ind = id;
ind2 = p->index;
}
}
int main()
{
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
scanf("%d", &n);
add(0, 1);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a);
xorp ^= a;
cauta(xorp, i);
add(xorp, i + 1);
}
printf("%d %d %d\n", maxsol, ind2, ind);
return 0;
}