Cod sursa(job #641062)

Utilizator andra23Laura Draghici andra23 Data 27 noiembrie 2011 02:46:51
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#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*MAXHEIGHT];

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 (height > 0) {
		return searchMax(nextNode, x, height-1, result);
	} 
	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;
}