Pagini recente » Cod sursa (job #3236161) | Cod sursa (job #2093133) | Cod sursa (job #678681) | Cod sursa (job #916634) | Cod sursa (job #1161535)
#include <cstdio>
using namespace std;
struct Trie {
int value;
Trie *edges [2];
Trie () {
value = 0;
edges [0] = NULL;
edges [1] = NULL;
}
};
const int N = 100001;
int n, a [N], XOR [N], index [N];
Trie *trie = new Trie;
void read () {
int i;
scanf ("%d", &n);
for (i = 1; i <= n; i ++)
scanf ("%d", &a [i]);
}
void insert (int x, int ind) {
int i, b;
Trie *node;
node = trie;
for (i = 21; i >= 0; i --) {
if (x & (1 << i))
b = 1;
else b = 0;
if (node -> edges [b] != NULL)
node = node -> edges [b];
else {
node -> edges [b] = new Trie;
node = node -> edges [b];
}
}
if (node -> value < ind)
node -> value = ind;
}
int query (int x) {
int i, b;
Trie *node;
node = trie;
for (i = 21; i >= 0; i --) {
if (x & (1 << i))
b = 0;
else b = 1;
if (node -> edges [b] != NULL)
node = node -> edges [b];
else
if (node -> edges [!b] != NULL)
node = node -> edges [!b];
else break;
}
if (i >= 0)
return 0;
else return node -> value;
}
void solve () {
int i, max = -1, st, dr, c;
XOR [1] = a [1];
index [1] = 0;
insert (XOR [1], 1);
for (i = 2; i <= n; i ++) {
XOR [i] = XOR [i - 1] ^ a [i];
index [i] = 0;
index [i] = query (XOR [i]);
insert (XOR [i], i);
}
for (i = 1; i <= n; i ++) {
if (index [i] == 0)
c = XOR [i];
else c = XOR [i] ^ XOR [index [i]];
if (c > max) {
max = c;
st = index [i] + 1;
dr = i;
}
else
if (c == max)
if (dr > i) {
dr = i;
st = index [i] + 1;
}
else
if (dr == i && dr - st + 1 > i) {
st = index [i] + 1;
dr = i;
}
}
printf ("%d %d %d\n", max, st, dr);
}
int main () {
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
read ();
solve ();
return 0;
}