Pagini recente » Cod sursa (job #2517772) | Cod sursa (job #2064125) | Cod sursa (job #2367601) | Cod sursa (job #101982) | Cod sursa (job #1694728)
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define B 21
#define MAX 100003
using namespace std;
struct trie {
trie *t0;
trie *t1;
int p;
};
ifstream in("xormax.in");
ofstream out("xormax.out");
trie *root;
int M[MAX];
void init(trie *&nod) {
nod = (trie*) malloc(sizeof(trie));
nod->t0 = NULL;
nod->t1 = NULL;
nod->p = -1;
}
trie* ins(trie *nod, int val, int poz, int bit) {
if(nod == NULL)
init(nod);
if(bit == -1) {
nod->p = poz;
return nod;
}
trie *next;
if((val&(1<<bit)) == 0) {
next = ins(nod->t0, val, poz, bit-1);
nod->t0 = next;
} else {
next = ins(nod->t1, val, poz, bit-1);
nod->t1 = next;
}
return nod;
}
int gm(trie *nod, int val, int bit) {
if(bit == -1)
return nod->p;
if((val&(1<<bit)) == 0) {
if(nod->t1 != NULL) {
return gm(nod->t1, val, bit-1);
} else {
return gm(nod->t0, val, bit-1);
}
} else {
if(nod->t0 != NULL) {
return gm(nod->t0, val, bit-1);
} else {
return gm(nod->t1, val, bit-1);
}
}
}
int main() {
init(root);
int n,val;
int X = 0;
int P;
int mx = 0;
int st = 1;
int en = 1;
in >> n;
ins(root, 0, 0, B);
for(int i = 1; i <= n; i++) {
in >> val;
X ^= val;
M[i] = X;
ins(root, X, i, B);
P = gm(root, X, B);
if(X^M[P] > mx || (X^M[P] == mx && en-st > i-P+1)) {
mx = X^M[P];
st = P+1;
en = i;
}
}
out << mx << " " << st << " " << en << '\n';
return 0;
}