Cod sursa(job #159936)

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

using namespace std;

#define act ((cur & i) ? (1) : (0))

class Node {
public:
	Node() :
		idx(0)
	{
		c[0] = c[1] = 0;
	}

	Node *c[2];
	int idx;
};

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

void insert_into_trie(int cur, int idx) {
	Node *n = &root;
	for (int i = 1 << 30; i > 0; i >>= 1) {
		if (!n->c[act])
			n->c[act] = new Node;
		n = n->c[act];
	}
	n->idx = idx;
}

int find_in_trie(int cur) {
	Node *n = &root;
	for (int i = 1 << 30; i > 0; i >>= 1) {
		if (n->c[!act]) {
			n = n->c[!act];
			continue;
		}

		if (n->c[act]) {
			n = n->c[act];
			continue;
		}
		
		return -1;
	}
	
	return n->idx;
}

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

	ofstream fout("xormax.out");
	fout << largest << " " << ms << " " << mf << endl;
	fout.close();

	return 0;
}