Cod sursa(job #2285737)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 19 noiembrie 2018 08:30:29
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#define DM 100001
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;

ifstream fi ("xormax.in");
ofstream fo ("xormax.out");
int n, cnt, v[DM], s[DM], mx, aux, lo, hi;
vector <int> crsp[DM];
struct trie {
	int poz;
	trie *son[2];
	trie() {
		memset(son, 0, sizeof son);
	}
};
trie *root = new trie();

void create(int poz, trie *nod) {
	int side = 0;
	trie *crt = nod;
	for (int i = 22; i >= 0; --i) {
		side = ((s[poz]&(1 << i)) != 0);
		if (crt->son[side] == 0) {
			crt->son[side] = new trie();
		}
		crt = crt->son[side];
	}
	crt->poz = poz;
}

int find(int x, trie *nod) {
	int rez = 0, side = 0;
	trie *crt = nod;
	for (int i = 22; i >= 0; --i) {
		side = ((x&(1 << i)) != 0);
		if (crt->son[side^1] == 0) {
			rez += ((1 << i)*side);
			crt = crt->son[side];
		} else {
			rez += ((1 << i)*(side^1));
			crt = crt->son[side^1];
		}
	}
	return crt->poz;
}

int main() {
	fi >> n;
	for (int i = 1; i <= n; ++i)
		fi >> v[i];
	create(0, root);
	for (int i = 1; i <= n; ++i) {
		s[i] = s[i-1]^v[i];
		aux = find(s[i], root);
		if (s[i]^s[aux] > mx || s[i]^s[aux] == mx && i - aux < hi - lo) {
			mx = s[i]^s[aux];
			lo = aux;
			hi = i;
		}
		create(i, root);
	}
	fo << mx << ' ' << lo + 1 << ' ' << hi;
	return 0;
}