Cod sursa(job #2774938)

Utilizator sebimihMihalache Sebastian sebimih Data 13 septembrie 2021 17:05:24
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct trie
{
	trie()
	{
		poz = 0;
		fiu[0] = fiu[1] = 0;
	}

	int poz = 0;
	trie* fiu[2];
};

const int MAXN = 1e5 + 5;

int sir[MAXN];
trie* radacina = new trie;

void adaugaNr(trie* nod, int index, int nivel)
{
	if (nivel < 0)
	{
		nod->poz = index;
		return;
	}

	int indexFiu = (sir[index] >> nivel) & 1;
	if (nod->fiu[indexFiu] == nullptr)
	{
		nod->fiu[indexFiu] = new trie;
	}

	adaugaNr(nod->fiu[indexFiu], index, nivel - 1);
}

// gaseste secventa pentru care : (secventa de la 1 la index - 1) XOR sir[index] = maxim
int getStartIndex(trie* nod, int index, int nivel)
{
	if (nivel < 0)
	{
		return nod->poz;
	}

	int indexFiu = ((sir[index] >> nivel) & 1) ^ 1;		// vreau opusul bit-ului la care suntem
	if (nod->fiu[indexFiu] == nullptr)					// daca nu avem opusul bit-ului la care suntem, il luam pe acelasi
	{
		indexFiu = indexFiu ^ 1;
	}

	return getStartIndex(nod->fiu[indexFiu], index, nivel - 1);
}

int main()
{
	int n;
	fin >> n;

	for (int i = 1; i <= n; i++)
	{
		fin >> sir[i];
		sir[i] = (sir[i - 1] ^ sir[i]);
	}

	adaugaNr(radacina, 0, 20);
	
	int maxSecventa = -1, maxStart = 0, maxStop = 0;
	for (int i = 1; i <= n; i++)
	{
		int stop = i;
		int start = getStartIndex(radacina, i, 20) + 1;
		int secventa = sir[stop] ^ sir[start - 1];

		if (secventa > maxSecventa)
		{
			maxSecventa = secventa;
			maxStart = start;
			maxStop = stop;
		}
		
		adaugaNr(radacina, i, 20);
	}

	fout << maxSecventa << ' ' << maxStart << ' ' << maxStop;
}