Pagini recente » Cod sursa (job #244195) | Cod sursa (job #318162) | Cod sursa (job #49371) | Cod sursa (job #2253551) | Cod sursa (job #1455371)
#include <iostream>
#include <fstream>
#include <assert.h>
const char IN[] = "xormax.in", OUT[] = "xormax.out";
const int NMAX = 100001;
const int ALPHABET = 2;
const int INF = 0x3f3f3f3f;
const int MAXBITRANK = 21;
struct node {
int index, succs_count;
node* succs[ALPHABET];
};
using namespace std;
int N;
node* trie;
int S[NMAX];
inline char get_bit(int const x, int rank) {
return ((0x1 << rank) & x) ? 1 : 0;
}
void add_word(node* crt, int x, int rank, int pos) {
if (rank == -1) {
++crt->index = pos;
return;
}
int key = get_bit(x, rank);
if (crt->succs[key] == NULL) {
++crt->succs_count;
crt->succs[key] = new node();
}
add_word(crt->succs[key], x, rank - 1, pos);
}
void set(int &x, int rank) {
x |= (0x1 << rank);
}
int find_flipped(node *crt, int x, int rank, int &s) {
if (rank == -1 || crt->succs_count == 0) return crt->index;
int key = 1 - (get_bit(x, rank));
if (crt->succs[key] == NULL) return find_flipped(crt->succs[1-key], x, rank-1, s);
set(s, rank);
return find_flipped(crt->succs[key], x, rank - 1, s);
}
inline void read_data() {
assert(freopen(IN, "r", stdin));
assert(scanf("%d", &N));
S[0] = 0;
int best = 0, index1 = 0, index2 = 0;
for (int i = 0, s = 0; i < N; ++i) {
int x;
assert(scanf("%d", &x));
S[i + 1] = S[i] ^ x;
s = 0;
int ind = find_flipped(trie, S[i+1], MAXBITRANK, s);
if (s > best) best = s, index1 = ind, index2 = i;
add_word(trie, S[i+1], MAXBITRANK, i);
}
fprintf(fopen(OUT, "w"), "%d %d %d\n", best, index1+2, index2+1);
fclose(stdin);
}
int main() {
trie = new node();
trie->index = -1;
trie->succs_count = 0;
read_data();
delete trie;
}