Cod sursa(job #1019182)

Utilizator dunhillLotus Plant dunhill Data 30 octombrie 2013 19:27:05
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define NMAX 100001

ifstream fin("xormax.in");
ofstream fout("xormax.out");

int i, j, N;
int ANS;
int st;
int dr;

int Conf[24];
int S[NMAX];

struct nod {
	int ind;
	nod *next[2];
};

nod *root, *T;

void init(nod *&root) {
	root = new nod;
	root->ind = 0;
	root->next[0] = NULL;
	root->next[1] = NULL;
}

void insert(nod *root, int Conf[], int n) {
	T = root;
	for (int i = 0; i <= n; ++i) {
		if (T->next[Conf[i]] == NULL) 
			init(T->next[Conf[i]]);
		T = T->next[Conf[i]];
	}
	T->ind = ::i;
}

void link(nod *root, int Conf[], int n) {
	T = root;
	for (int i = 0; i <= n; ++i) {
		if (T->next[Conf[i] ^ 1] != NULL) 
			T = T->next[Conf[i] ^ 1];
		else
			T = T->next[Conf[i]];
	}
	if (S[::i] ^ S[T->ind] > ANS)
		ANS = S[T->ind] ^ S[::i], st = T->ind, dr = ::i;
}

int main() {
	fin >> N;
	init(root);
	for (i = 1; i <= N; ++i) {
		fin >> S[i];
		S[i] ^= S[i - 1];
		for (j = 21; j >= 0; --j)
			if (S[i] & (1 << j))
				Conf[j] = 1;
			else
				Conf[j] = 0;
		reverse(Conf, Conf + 23);
		insert(root, Conf, 21);
		link(root, Conf, 21);
	}
	fout << ANS << ' ' << st + 1 << ' ' << dr << '\n';
	return 0;
}