Cod sursa(job #1655973)

Utilizator krityxAdrian Buzea krityx Data 18 martie 2016 16:16:23
Problema Xor Max Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <bitset>

using namespace std;

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

class TrieNode
{
public:
	unsigned int elementCount, nChildren;
	int index;
	vector<TrieNode*> children;
	TrieNode()
	{
		elementCount = 0;
		nChildren = 0;
		children.resize(2);
	}
};

class Trie
{
public:
	TrieNode* root;
	int maxDepth;
	Trie(int depth)
	{
		root = new TrieNode;
		maxDepth = depth;
	}
	void Add(int b, int ind)
	{
		TrieNode *current = root;
		for (int i = maxDepth - 1; i >= 0; i--)
		{
			int idx = (b & (1 << i)) > 0;
			if (current->children[idx])
			{
				current = current->children[idx];
			}
			else
			{
				TrieNode* node = new TrieNode;
				current->nChildren++;
				current->children[idx] = node;
				current = node;
			}
			if (i == 0)
			{
				current->index = ind;
				current->elementCount++;
			}
		}
	}

	int findMaxXorIndex(bitset<22> b)
	{
		TrieNode *current = root;

		for (int i = maxDepth - 1; i >= 0; i--)
		{
			int idx = !b[i];
			if (current->children[idx])
			{
				current = current->children[idx];
			}
			else if (current->children[!idx])
			{
				current = current->children[!idx];
			}
			else return 0;
		}

		return current->index;
	}
	
};

int getBitsetMinSize(int x)
{
	return floorLog2(x) + 1;
}

int main()
{
	int n, x, i, maxSize = 0;
	vector<int> pXor;

	ifstream f("xormax.in");
	f >> n;
	pXor.resize(n + 1);
	pXor[0] = 0;
	for (i = 1; i <= n; i++)
	{
		f >> x;
		pXor[i] = pXor[i - 1] ^ x;
	}

	int max = pXor[1];
	int start, end;
	start = end = 1;

	Trie t(22);

	for (int i = 1; i <= n; i++)
	{
		t.Add(pXor[i], i);
		int maxXorIndex = t.findMaxXorIndex(pXor[i]);
		int r = (pXor[i] ^ pXor[maxXorIndex]);
		if (r > max)
		{
			max = r;
			start = maxXorIndex + 1;
			end = i;
		}
	}
	f.close();

	ofstream g("xormax.out");
	g << max << " " << start << " " << end;
	g.close();
	return 0;
}