Cod sursa(job #1569307)

Utilizator krityxAdrian Buzea krityx Data 15 ianuarie 2016 12:22:05
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <vector>
#include <cmath>
#define NMAX 100004
using namespace std;

int floorLog2(int x)
{
	if (x == 0) return -1;
	return (int)floor(log2(x));
}

int main()
{
	int n, i, j, sol = -1, startIndex = 1, endIndex = 1, solmax;
	vector<int> a, partialXor, pos;
	a.resize(NMAX);
	partialXor.resize(NMAX);
	pos.resize(NMAX);
	partialXor[0] = 0;
	ifstream f("xormax.in");
	f >> n;
	for (i = 1; i <= n; i++)
	{
		f >> a[i];
		partialXor[i] = partialXor[i - 1] ^ a[i];
	}
	f.close();
	i = 1; j = 1;
	sol = solmax = a[1];
	pos[floorLog2(a[1])] = 1;
	while (j <= n)
	{
		j++;
		if (a[j] == 0)
		{
			sol = a[j + 1];
			i = j = j + 1;
			int l2 = floorLog2(a[j]);
			if (l2 > 0)
			{
				pos[l2] = j;
			}
		}
		else
		{
			int l2 = floorLog2(a[j]);
			if (pos[l2] == 0)
			{
				sol = sol ^ a[j];

			}
			else
			{
				i = pos[l2] + 1;
				sol = partialXor[j] ^ partialXor[i - 1];

			}
			if (sol > solmax)
			{
				solmax = sol;
				startIndex = i;
				endIndex = j;
			}
		}
	
	}

	ofstream g("xormax.out");
	g << solmax << " " << startIndex << " " << endIndex;
	g.close();
	return 0;
}