Pagini recente » Cod sursa (job #670550) | Cod sursa (job #1435086) | Cod sursa (job #344448) | Cod sursa (job #2928496) | Cod sursa (job #641060)
Cod sursa(job #641060)
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
const int MAXN = 100010;
const int MAXHEIGHT = 23;
const int SIGMA = 2;
int trie[MAXN*MAXHEIGHT][SIGMA];
int a[MAXN], position[MAXN];
void insertNumber(int node, int x, int height, int &nodes, int i) {
int value = (x & (1<<height)) >> height;
assert(0 <= value && value <= 1);
if (trie[node][value] == 0) {
nodes++;
assert(nodes <= MAXN*MAXHEIGHT);
trie[node][value] = nodes;
}
int nextNode = trie[node][value];
if (height > 0) {
insertNumber(nextNode, x, height-1, nodes, i);
} else {
position[node] = i;
}
}
int searchMax(int node, int x, int height, int &result) {
int value = 1 - ((x & (1<<height)) >> (height));
assert(0 <= value && value <= 1);
int nextNode = 0;
if (trie[node][value] != 0) {
result = result | (1 << height);
nextNode = trie[node][value];
} else {
nextNode = trie[node][1-value];
}
assert(nextNode > 0 || height == 0);
if (nextNode > 0 && height > 0) {
return searchMax(nextNode, x, height-1, result);
} else {
return position[node];
}
}
int main() {
ifstream f("xormax.in");
ofstream g("xormax.out");
int n;
f >> n;
for (int i = 1; i <= n; i++) {
f >> a[i];
}
int height = 22;
int nodes = 1;
insertNumber(1, 0, height, nodes, 0);
int result = -1, rstart, rend;
for (int i = 1; i <= n; i++) {
a[i] = a[i]^a[i-1];
int x = 0;
int start = searchMax(1, a[i], height, x) + 1;
if (x > result) {
result = x;
rstart = start;
rend = i;
}
insertNumber(1, a[i], height, nodes, i);
}
g << result << " " << rstart << " " << rend << '\n';
return 0;
}