Cod sursa(job #2274843)

Utilizator flibiaVisanu Cristian flibia Data 2 noiembrie 2018 16:22:58
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#define N 20

using namespace std;

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

struct nod {
	int mx;
	nod *son[2];
	nod () {
		mx = 0;
		memset(son, 0, sizeof son);
	}
};

int n, xo, x, bst, st = 1, dr = 1;
nod *root = new nod();

void baga(nod *x, int p, int nr, int cur) {
	if (p == -1) {
		x -> mx = cur;
		return;
	}
	int bit = (nr & (1 << p)) != 0;
	if (x -> son[bit] == NULL)
		x -> son[bit] = new nod();
	baga(x -> son[bit], p - 1, nr, cur);
}

void dive(nod *x, int p, int nr, int cur, int gain) {
	if (p == -1) {
		if (gain > bst) {
			bst = gain;
			st = x -> mx + 1;
			dr = cur;
		}
		return;
	}
	int bit = (nr & (1 << p)) != 0;
	if (x -> son[!bit] != NULL)
		dive(x -> son[!bit], p - 1, nr, cur, (gain | (1 << p))); 
	else dive(x -> son[bit], p - 1, nr, cur, gain);
}

int main() {
	in >> n;
	for (int i = 1; i <= n; i++) {
		in >> x;
		xo ^= x;
		if (i > 1)
			dive(root, N, xo, i, 0);
		else bst = x;
		baga(root, N, xo, i); 
	}
	out << bst << ' ' << st << ' ' << dr;
	return 0;
}