Pagini recente » Cod sursa (job #2919733) | Cod sursa (job #82627) | Cod sursa (job #1833138) | Cod sursa (job #765419) | Cod sursa (job #500745)
Cod sursa(job #500745)
#include <stdio.h>
#include <string>
#define FISIN "xormax.in"
#define FISOUT "xormax.out"
#define MAXN 100001
int n;
int a[MAXN], pref[MAXN];
int best = -1, bstart, bend;
struct node {
node() { child[0] = child[1] = NULL; }
typedef node* pnode;
int poz;
pnode child[2];
} *root;
void insert(int poz, int num) {
node* n = root;
for (int i = 20; i >= 0; --i) {
int bit = num & (1 << i) ? 1 : 0;
if (!n->child[bit]) n->child[bit] = new node();
n = n->child[bit];
}
n->poz = poz;
}
int find_best_match(int num) {
node *n = root;
for (int i = 20; i >= 0; --i) {
int bit = num & (1 << i) ? 0 : 1;
n = n->child[bit] ? n->child[bit] : n->child[bit ^ 1];
}
return n->poz;
}
void print_tree(node *n, std::string pref) {
if (!n->child[0] && !n->child[1]) {
printf("%s -> %d\n", pref.c_str(), n->poz);
}
if (n->child[0]) print_tree(n->child[0], pref + "0");
if (n->child[1]) print_tree(n->child[1], pref + "1");
}
int main() {
root = new node();
insert(0, 0);
FILE *f = fopen(FISIN, "rt");
fscanf(f, "%d", &n);
pref[0] = 0;
for (int i = 1; i <= n; ++i) {
fscanf(f, "%d", a + i);
pref[i] = pref[i - 1] ^ a[i];
int poz = find_best_match(pref[i]);
int now = pref[i] ^ pref[poz];
if (now > best) {
best = now;
bstart = poz + 1;
bend = i;
}
insert(i, pref[i]);
}
fclose(f);
// print_tree(root, "");
f = fopen(FISOUT, "wt");
fprintf(f, "%d %d %d\n", best, bstart, bend);
fclose(f);
return 0;
}