Pagini recente » Cod sursa (job #1008719) | Cod sursa (job #2761837) | Cod sursa (job #1008312) | Cod sursa (job #1112058) | Cod sursa (job #1306268)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("xormax.in");
ofstream g ("xormax.out");
const int PMAX = 20;
const int NMAX = 100000 + 1;
struct Trie {
int nr;
Trie *fiu[2];
Trie() {
nr = 0;
fiu[0] = fiu[1] = NULL;
}
};
int n;
Trie *t;
int xor_sum[NMAX];
Trie *insereaza(int bit, int x, int i, Trie *t) {
if (t == NULL) t = new Trie();
if (bit == -1) {
t->nr = i;
return t;
}
int mask = x & (1 << bit);
mask = (mask != 0);
t->fiu[mask] = insereaza(bit - 1, x, i, t->fiu[mask]);
return t;
}
int sol(int bit, int x, Trie *t) {
if (t == NULL) return 0;
if (bit == -1) return t->nr;
int mask = x & (1 << bit);
mask = (mask != 0);
if (t->fiu[1 - mask] != NULL) return sol(bit - 1, x, t->fiu[1 - mask]);
return sol(bit - 1, x, t->fiu[mask]);
}
void rezolva() {
int j, rez = -1, a, b;
f >> n;
t = insereaza(PMAX, 0, 0, t);
for (int i = 1; i <= n; i++) {
f >> xor_sum[i];
xor_sum[i] ^= xor_sum[i - 1];
j = sol(PMAX, xor_sum[i], t);
if ((xor_sum[i] ^ xor_sum[j]) > rez) {
rez = xor_sum[i] ^ xor_sum[j];
a = j + 1;
b = i;
}
t = insereaza(PMAX, xor_sum[i], i, t);
}
g << rez << ' ' << a << ' ' << b << '\n';
}
int main() {
rezolva();
return 0;
}