Pagini recente » Cod sursa (job #535215) | Cod sursa (job #3164280) | Cod sursa (job #473901) | Cod sursa (job #1989556) | Cod sursa (job #3145179)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define NMAX 100005
int n;
int v[NMAX], aux[25];
int maxim, l, r;
struct trie {
int poz;
trie *v[2];
trie() {
poz = 0;
memset(v, 0, sizeof(v));
}
} *Q;
void query(int poz) {
memset(aux, 0, sizeof(aux));
int x = v[poz];
for (int k = 0; k <= 21; ++k) {
aux[21 - k + 1] = x % 2;
x /= 2;
}
trie *j = Q;
int sum = 0;
for (int i = 0; i <= 21; ++i) {
if (j->v[(aux[i] ^ 1)] != 0) {
sum += (1 << (21 - i + 1));
j = j->v[(aux[i] ^ 1)];
} else {
j = j->v[(aux[i])];
}
}
if (sum > maxim) {
maxim = sum;
l = j->poz + 1;
r = poz;
if (l == 0) {
l = 1;
}
if (r == 0) {
r = 1;
}
if (r < l) {
r = l;
}
}
}
void update(int poz) {
memset(aux, 0, sizeof(aux));
int x = v[poz];
for (int k = 0; k <= 21; ++k) {
aux[21 - k + 1] = x % 2;
x /= 2;
}
trie *j = Q;
for (int i = 0; i <= 21; ++i) {
if (j->v[(aux[i])] != 0) {
j = j->v[(aux[i])];
} else {
j->v[(aux[i])] = new trie;
j = j->v[(aux[i])];
}
}
j->poz = poz;
}
int main() {
Q = new trie;
update(0);
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> v[i];
v[i] ^= v[i - 1];
query(i);
update(i);
}
fout << maxim << ' ' << l << ' ' << r;
return 0;
}