Cod sursa(job #159907)

Utilizator scvalexAlexandru Scvortov scvalex Data 14 martie 2008 15:10:40
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>

using namespace std;

class Node {
public:
	Node() :
		left(0),
		right(0),
		idx(0)
	{
	}

	Node *left, *right;
	int idx;
};

int N;
int A[100001];
Node root;

void insert_into_trie(int cur, int idx) {
	int i = 1 << 22;

	Node *n = &root;
	while (i > 0) {
		if (i & cur) {
			if (!n->right)
				n->right = new Node;
			n = n->right;
		} else {
			if (!n->left)
				n->left = new Node;
			n = n->left;
		}

		i >>= 1;
	}
	n->idx = idx;
}

int find_in_trie(int cur) {
	int i = 1 << 22;

	Node *n = &root;
	while (i > 0) {
		if (i & cur) {
			if (n->left)
				n = n->left;
			else
				n = n->right;
		} else {
			if (n->right)
				n = n->right;
			else
				n = n->left;
		}

		i >>= 1;
	}
	
	return n->idx;
}

#define MIN(a, b) ((a > b) ? (b) : (a))
#define MAX(a, b) ((a > b) ? (a) : (b))

int main(int argc, char *argv[]) {
	FILE *fi = fopen("xormax.in", "r");
	fscanf(fi, "%d", &N);
	int aux;
	int cur(0);
	for (int i(0); i < N; ++i) {
		fscanf(fi, "%d", &aux);
		A[i] = cur ^= aux;
		//cout << cur << endl;
		insert_into_trie(cur, i);
	}
	fclose(fi);

	int largest(-1),
		ms, mf;
	for (int i(0); i < N; ++i) {
		//cout << A[i] << " ";
		int aux = find_in_trie(A[i]);
		//cout << A[aux] << endl;
		if (A[i] ^ A[aux] > largest) {
			largest = A[i] ^ A[aux];
			ms = aux;
			mf = i;
		}
	}

	ofstream fout("xormax.out");
	fout << (A[ms] ^ A[mf]) << " " << MIN(ms, mf) + 2 << " " << MAX(ms, mf) + 1 << endl;
	fout.close();

	return 0;
}