Cod sursa(job #1833485)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 22 decembrie 2016 14:17:04
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <queue>
#define lgmax 23
using namespace std;

typedef struct Nod * Arbore;
struct Nod
{
	int h;
	vector <int> poz;
	Arbore st = 0, dr = 0; /// st -> 0
	Nod() { }
	Nod(int x, int _h, int _poz)
	{
		h = _h;
		if (h != 1) {
			if ((x & 1))
				dr = new Nod(x / 2, h - 1, _poz);
			else
				st = new Nod(x / 2, h - 1, _poz);
		}
		else
			poz.push_back(_poz);
	}
	void insert(int x, int _poz)
	{
		if (h != 1) {
			if ((x & 1)) {
				if (dr == 0)
					dr = new Nod(x / 2, h - 1, _poz);
				else
					dr->insert(x / 2, _poz);
			}
			else {
				if (st == 0)
					st = new Nod(x / 2, h - 1, _poz);
				else
					st->insert(x / 2, _poz);
			}
		}
		else
			poz.push_back(_poz);
	}
};

int inv(int x);
void proc(vector <pair <int, int>> & v);

int nr[100010];
queue <pair <Arbore, Arbore>> q;

int main()
{
	ifstream in("xormax.in");
	int n;
	in >> n;
	
	Arbore k = new Nod;
	k->h = lgmax + 1;
	
	for (int i(1); i <= n; i++) {
		in >> nr[i];
		nr[i] ^= nr[i - 1];
		k->insert(inv(nr[i]), i);
	}

	q.push({ k, k });

	vector <pair <int, int>> v;
	proc(v);

	int a, b, best(0);

	for (auto i : v) {
		if ((nr[i.first] ^ nr[i.second]) > best)
			best = (nr[i.first] ^ nr[i.second]), a = i.first, b = i.second;
		else if ((nr[i.first] ^ nr[i.second]) == best && i.second - i.first < b - a)
			a = i.first, b = i.second;
	}

	ofstream out("xormax.out");

	out << best << ' ' << a + 1 << ' ' << b;
	return 0;
}

void proc(vector <pair <int, int>> & v)
{
	while (!q.empty()) {
		Arbore x(q.front().first), y(q.front().second);
		q.pop();

		if (x->poz.size() != 0) {
			for (int i(0); i < x->poz.size(); i++) {
				for (int j(0); j < y->poz.size(); j++) {
					if (x->poz[i] < y->poz[j])
						v.push_back({ x->poz[i], y->poz[j] });
					else
						v.push_back({ y->poz[j], x->poz[i] });
				}
			}
			continue;
		}

		if (x->st && x->dr && y->st && y->dr) {
			q.push({ x->st, y->dr });
			q.push({ x->dr, y->st });
		}
		else {
			if (x->st && !x->dr) {
				if (y->dr)
					q.push({ x->st, y->dr });
				else
					q.push({ x->st, y->st });
			}
			else if (x->dr && !x->st) {
				if (y->st)
					q.push({ x->dr, y->st });
				else
					q.push({ x->dr, y->dr });
			}
			else {
				if (y->st)
					q.push({ x->dr, y->st });
				else
					q.push({ x->st, y->dr });
			}
		}
	}
}


int inv(int x)
{
	int r(0);
	for (int i(0); i < lgmax; i++) {
		r <<= 1;
		r |= (x & 1);
		x >>= 1;
	}
	return r;
}