Pagini recente » Cod sursa (job #88074) | Cod sursa (job #1088055) | Cod sursa (job #1650831) | Cod sursa (job #3137046) | Cod sursa (job #633864)
Cod sursa(job #633864)
#include <stdio.h>
#include <string.h>
#define MaxN 100000
struct trie_node {
struct trie_node *child[2];
int idx;
};
int n;
int soli, solj, solmax;
inline void trie_insert(struct trie_node *root, int value, int idx) {
int bit;
struct trie_node *tmp = root;
for (bit = 1 << 21 ; bit > 0 ; bit >>= 1) {
int cur_bit = !(value & bit);
if (tmp -> child[cur_bit] == NULL)
tmp -> child[cur_bit] = (struct trie_node *)calloc(1, sizeof(struct trie_node));
tmp = tmp -> child[cur_bit];
}
tmp -> idx = idx;
}
void solve(void) {
int i, bit, val, sum, t;
struct trie_node* tmp, *trie_root;
freopen("xormax.in", "r", stdin);
scanf("%d\n", &n);
scanf("%d ", &sum);
trie_root = (struct trie_node *)calloc(1, sizeof(struct trie_node));
trie_insert(trie_root, sum, 0);
solmax = sum;
for (i = 1 ; i < n ; i++) {
scanf("%d ", &t);
sum ^= t;
tmp = trie_root;
val = 0;
for (bit = 1 << 21 ; bit > 0 ; bit >>= 1) {
int rev_cur_bit = !!(sum & bit);
if (tmp -> child[rev_cur_bit] == NULL)
tmp = tmp -> child[!rev_cur_bit];
else {
tmp = tmp -> child[rev_cur_bit];
val ^= bit;
}
}
trie_insert(trie_root, sum, i);
if (val > solmax) {
solmax = val;
solj = i;
soli = tmp -> idx + 1;
}
}
}
void write(void) {
freopen("xormax.out", "w", stdout);
printf("%d %d %d\n", solmax, soli + 1, solj + 1);
}
int main(void) {
solve();
write();
return 0;
}