Cod sursa(job #641061)

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

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;
}