Cod sursa(job #1655838)

Utilizator krityxAdrian Buzea krityx Data 18 martie 2016 13:29:08
Problema Xor Max Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 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;
	Trie()
	{
		root = new TrieNode;
	}
	void Add(bitset<22> b, int ind)
	{
		TrieNode *current = root;
		for (int i = b.size() - 1; i >= 0; i--)
		{
			int idx = b[i];
			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 = b.size() - 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];
			}
		}

		return current->index;
	}
	
};

string pad(int x, int n)
{
	bitset<32> bset;
	return "";
}

int main()
{
	int n, x, i;
	vector<bitset<22>> v, pXor;
	Trie t;

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

	int max = pXor[1].to_ulong();
	int start, end;
	start = end = 1;

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

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