Cod sursa(job #1835282)

Utilizator mihai.alphamihai craciun mihai.alpha Data 26 decembrie 2016 17:23:05
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
class trie{
	public:
	int inf;
	trie *son[2];
	trie() {
		inf = 0;
		for(int i = 0;i < 2;i++)
			son[i] = NULL;
	}
	void add(int x, int bit, int poz){
		int extr;
		if(bit == -1)  {
			if(poz > inf)
				inf = poz;
		}
		else  {
			extr = (x & (1 << bit)) > 0;
			if(son[extr] == NULL)
				son[extr] = new trie;
			son[extr] -> add(x, bit - 1, poz);
		}
	}
};
FILE *fin, *fout;
int main()  {
	fin = fopen("xormax.in", "r");
	fout = fopen("xormax.out", "w");
	int n, max, st, dr, extr, bst;
	trie *t, *cursor;
	t = new trie;
	t -> add(0, 20, 1);
	int s = 0;
	max = -1, st = -1, dr = -1;
	fscanf(fin, "%d", &n);
	for(int i = 1;i <= n;i++)  {
		int x;
		fscanf(fin, "%d", &x);
		s = s ^ x;
		cursor = t;
		bst = 0;
		for(int j = 20;j >= 0;j--)  {
			extr = (s & (1 << j)) > 0;
			if(cursor -> son[1 - extr] != NULL)  {
				bst = (bst << 1) | 1;
				cursor = cursor -> son[1 - extr];
			}
			else {
				bst = bst << 1;
				cursor = cursor -> son[extr];
			}
		}
		if(max < bst)
			max = bst, dr = i, st = cursor -> inf;
		t -> add(s, 20, i + 1);
	}
	fprintf(fout, "%d %d %d", max, st, dr);
	fclose(fin);
	fclose(fout);
	return 0;
}