Cod sursa(job #2737190)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 4 aprilie 2021 15:10:15
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
using namespace std;

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

struct trie
{
	int ind = 0;
	trie *f[2] = {};
};

trie *t = new trie;

void pune (trie *nod, int x, int h, int ind)
{
	if (h == -1)
		nod -> ind = ind;
	else
	{
		if (nod -> f[(x>>h)&1] == NULL)
			nod -> f[(x>>h)&1] = new trie;
		pune (nod -> f[(x>>h)&1], x, h-1, ind);
	}
}

pair <int, int> cauta (trie *nod, int &x, int h)
{
	if (h == -1)
		return {0, nod -> ind};
	else
	{
		pair <int, int> rasp;
		if (nod -> f[((x>>h)&1)^1] == NULL)
		{
			rasp = cauta (nod -> f[(x>>h)&1], x, h-1);
			return {(((x>>h)&1)<<h) + rasp.first, rasp.second};
		}
		rasp = cauta (nod -> f[((x>>h)&1)^1], x, h-1);
		return {((((x>>h)&1)^1)<<h) + rasp.first, rasp.second};
	}
}

int a[100001], x[100001];

int main()
{
	int i, n, raspval = -1;
	pair <int, int> alo, raspint;
	fin >> n;
	for (i = 1; i<=n; i++)
	{
		fin >> a[i];
		x[i] = x[i-1] ^ a[i];
	}
	pune(t, 0, 20, 0);
	for (i = 1; i<=n; i++)
	{
		alo = cauta (t, x[i], 20);
		if ((alo.first ^ x[i]) > raspval)
		{
			raspval = alo.first ^ x[i];
			raspint = {alo.second + 1, i};
		}
		pune(t, x[i], 20, i);
	}
	fout << raspval << ' ' << raspint.first << ' ' << raspint.second;
	return 0;
}