Pagini recente » Cod sursa (job #1856890) | Cod sursa (job #838418) | Cod sursa (job #2483497) | Cod sursa (job #110621) | Cod sursa (job #641058)
Cod sursa(job #641058)
#include <iostream>
#include <fstream>
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;
if (trie[node][value] == 0) {
nodes++;
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));
int nextNode = 0;
if (trie[node][value] != 0) {
result = result | (1 << height);
nextNode = trie[node][value];
} else {
nextNode = trie[node][1-value];
}
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 = 0, rstart, rend;
for (int i = 1; i <= n; i++) {
a[i] = a[i]^a[i-1];
int x = a[i];
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);
}
cout << result << " " << rstart << " " << rend << '\n';
return 0;
}