Cod sursa(job #634363)

Utilizator calinuxIorgulescu Calin calinux Data 16 noiembrie 2011 02:06:18
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string.h>

#define MAXN 		100001
#define MAX_BITS	21

using namespace std;

typedef unsigned int uint32;

struct TrieData
{
	long index;
	TrieData *child[2];
};

class CTrie
{
public:
	CTrie()
	{
		memset(Trie.child, 0, 2*sizeof(TrieData*));
	}
	
	inline void addElement(const uint32 num, const int index)
	{
		uint32 i;
		int childIndex;
		TrieData *ptr = &Trie;
		
		for (i = 1<<MAX_BITS; i; i>>=1)
		{
			childIndex = !(!(num & i));

			if (!ptr->child[childIndex])
			{
				ptr->child[childIndex] = allocElement();
			}
			
			ptr = ptr->child[childIndex];
		}
		
		ptr->index = index;
	}
	
	long findMaximizingElement(const uint32 num, uint32& val) const
	{
		uint32 i;
		int childIndex;
		const TrieData *ptr = &Trie;
		
		val = 0;

		for (i = 1<<MAX_BITS; i; i>>=1)
		{
			childIndex = !(num & i);
			
			if (ptr->child[childIndex])
			{
				val += i;
				ptr = ptr->child[childIndex];
			}
			else
				ptr = ptr->child[!childIndex];
		}
		
		return ptr->index;
	}

private:
	TrieData Trie;
	
	inline TrieData* allocElement() const
	{
		TrieData *elem = new TrieData;

		memset(elem->child, 0, 2*sizeof(TrieData*));
		
		return elem;
	}
};

int main()
{
	unsigned long x;
	uint32 sum = 0;
	long maxsum, indMin = 0, indMax=MAXN, N;
	fstream fin("xormax.in", fstream::in);
	fstream fout("xormax.out", fstream::out);
	CTrie Trie;
	
	fin>>N;
	
	fin >> x;
	
	maxsum = x;
	indMax = indMin = 0;
	
	Trie.addElement(0, -1);
	Trie.addElement(sum, 0);
	
	for (int i=1; i<N; ++i)
	{
		long index;
		uint32 val;

		fin >> x;
		
		index = Trie.findMaximizingElement(sum, val);
		sum ^= x;

		Trie.addElement(sum, i);

		if (val > maxsum)
		{
			maxsum = val;
			indMin = index+1;
			indMax = i-1;
		}
	}

	fout << maxsum << " " << indMin+1 << " " << indMax+1 << endl;
	
	
	fin.close();
	fout.close();
	return 0;
}