Cod sursa(job #1251158)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 28 octombrie 2014 23:38:39
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#define DIM 100005
#define DIMB 25
#define infile "xormax.in"
#define outfile "xormax.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int n, nr;

int code, step;

int v[DIMB], Partial_Xor[DIM];

struct trie {
	int pos;
	trie *fii[2];
	trie() {
		pos = 0;
		fii[1] = fii[0] = NULL;
	}
} *Root = new trie;

void Update_Trie(trie *nod, int *i) {
	if (*i == -1) {
		nod->pos = step;
		return;
	}
	if (nod->fii[*i] == NULL)
		nod->fii[*i] = new trie;
	Update_Trie(nod->fii[*i], i + 1);
}

int Query_Trie(trie *nod, int *i) {
	if (*i == -1)
		return nod->pos;
	code <<= 1;
	if (nod->fii[(*i) ^ 1] != NULL) {
		++code;
		return Query_Trie(nod->fii[(*i) ^ 1], i + 1);
	}
	return Query_Trie(nod->fii[(*i)], i + 1);
}

int main() {
	v[22] = -1;
	f >> n;
	for (int i = 1; i <= n; ++i) {
		f >> nr;
		Partial_Xor[i] = (Partial_Xor[i - 1] ^ nr);
	}
	Update_Trie(Root, v + 1);
	int Max = 0, right_end, left_end;
	for (int i = 1; i <= n; ++i) {
		nr = Partial_Xor[i];
		for (int j = 1; j <= 21; ++j)
			v[j] = ((nr & (1 << (21 - j))) == 0 ? 0 : 1);
		code = 0; step = i;
		int pos = Query_Trie(Root, v + 1);
		if (code > Max) {
			Max = code;
			left_end = pos + 1;
			right_end = i;
		}
		Update_Trie(Root, v + 1);
	}
	g << Max << " " << left_end << " " << right_end;
	return 0;
}