Cod sursa(job #1833704)

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

typedef struct Nod * Arbore;
struct Nod
{
	int h;
	int poz_min = 1e9, poz_max = -1;
	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 {
			if (_poz < poz_min)
				poz_min = _poz;
			if (_poz > poz_max)
				poz_max = _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 {
			if (_poz < poz_min)
				poz_min = _poz;
			if (_poz > poz_max)
				poz_max = _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;
	
	k->insert(0, 0);

	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 (i.first > i.second)
			swap(i.first, i.second);
	}

	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->h == 1) {
			if (x->poz_min != 1e9) {
				if (y->poz_min != 1e9)
					v.push_back({ x->poz_min, y->poz_min });
				if (y->poz_max != -1)
					v.push_back({ x->poz_min, y->poz_max });
			}
			if (x->poz_max != -1) {
				if (y->poz_min != 1e9)
					v.push_back({ x->poz_max, y->poz_min });
				if (y->poz_max != -1)
					v.push_back({ x->poz_max, y->poz_max });
			}
			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;
}