Pagini recente » Cod sursa (job #221240) | Cod sursa (job #364095) | Cod sursa (job #3122506) | Cod sursa (job #1531085) | Cod sursa (job #459564)
Cod sursa(job #459564)
#include <stdio.h>
int t[1<<22];
int a[100100], n;
int best, start, stop;
void read() {
FILE *f = fopen("xormax.in", "r");
fscanf(f, "%d", &n);
int i;
for (i = 1; i <= n; ++i)
fscanf(f, "%d" , a+i);
fclose(f);
}
void solve() {
int i, j;
for (i = 0; i < (1<<22); ++i)
t[i] = -1;
t[0] = 0;
int xor_sum = 0;
for (i = 1; i <= n; ++i) {
xor_sum ^= a[i];
//querry
int tree_index = 0;
for (j = 21; j >= 0; --j) {
if (t[tree_index + ((xor_sum & (1<<j)) ^ (1<<j))] >= 0)
tree_index += ((xor_sum & (1<<j)) ^ (1<<j));
else
tree_index += (xor_sum & (1<<j));
}
if (best < (tree_index ^ xor_sum)) {
best = (tree_index ^ xor_sum);
stop = i;
start = t[tree_index] + 1;
}
//update
tree_index = 0;
for (j = 21; j >= 0; --j) {
tree_index += xor_sum & (1<<j);
t[tree_index] = i;
}
}
}
void write() {
FILE *f = fopen("xormax.out", "w");
fprintf(f, "%d %d %d\n", best, start, stop);
fclose(f);
}
int main() {
read();
solve();
write();
return 0;
}