Cod sursa(job #605321)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 27 iulie 2011 20:32:52
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string.h>

#define MAXN 		100001
#define MAX_BITS	30

using namespace std;

typedef unsigned int uint32;

uint32 sums[MAXN];

struct TrieData
{
	vector<long> vIndex;
	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->vIndex.push_back(index);
	}
	
	const vector<long>* findMaximizingElement(const uint32 num) const
	{
		uint32 i;
		int childIndex;
		const TrieData *ptr = &Trie;
		
		for (i = 1<<MAX_BITS; i; i>>=1)
		{
			childIndex = !(num & i);
			
			if (ptr->child[childIndex])
				ptr = ptr->child[childIndex];
			else
				ptr = ptr->child[!childIndex];
		}
		
		return &ptr->vIndex;
	}

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, 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;
	//cout<<N<<endl;
	
	maxsum=-1;
	
	for (int i=0; i<N; ++i)
	{
		fin >> x;

		sum^=x;
		
		sums[i] = sum;
		
		//cout << sums[i] << " ";
		
		Trie.addElement(sums[i], i);
	}
	//cout<<endl;
	
	/*for (int i=0; i<N; ++i)
	{
		for (int j=i+1; j<N; ++j)
		{
			if ((int)(sums[j]^sums[i]) >= maxsum)
			{
				maxsum = (sums[j]^sums[i]);
				cout << maxsum << " " << i << " " << j << endl;
			}
		}
	}
	
	cout << endl;
	
	cout << "Ref maxsum = " << maxsum << endl;
	
	maxsum = -1;*/
	
	for (int i=0; i<N; ++i)
	{
		const vector<long> *ptr = Trie.findMaximizingElement(sums[i]);
		
		for (uint32 j=0; j<ptr->size(); j++)
		{
			int index = (*ptr)[j];
			int ii = i;
			
			if (index > ii)
			{
				index ^= ii;
				ii ^= index;
				index ^= ii;
			}
			
			if ((int)(sums[ii]^sums[index]) > maxsum)
			{
				maxsum = sums[ii]^sums[index];
				indMin = index;
				indMax = ii;
			}
			else if ((int)(sums[ii]^sums[index]) == maxsum)
			{
				long auxMin, auxMax;
				//i>index ? (auxMin = index+1, auxMax = i) : (auxMin = i+1, auxMax = index);
				auxMin = index;
				auxMax = ii;
				
				if (auxMax < indMax)
				{
					indMin = auxMin;
					indMax = auxMax;
				}
				else if (auxMax == indMax)
				{
					if ((auxMax - auxMin) < (indMax - indMin))
					{
						indMin = auxMin;
						indMax = auxMax;
					}
				}
			}
		}
	}
	
	fout << maxsum << " " << indMin+2 << " " << indMax+1 << endl;
	
	
	fin.close();
	fout.close();
	return 0;
}