Cod sursa(job #1001237)

Utilizator ChallengeMurtaza Alexandru Challenge Data 24 septembrie 2013 19:22:09
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
/*
	PROB: infoarena
	LANG: C++
*/

#include <fstream>

//#define DEBUG

#ifndef DEBUG
	#define PRINT(x)
	#define D if(0)
#else
	#include <iostream>
	#define PRINT(x) \
		cout<<#x<<":\t"<<x<<endl
	#define D if(1)
#endif

using namespace std;

const char InFile[]="xormax.in";
const char OutFile[]="xormax.out";
const int MaxN=21;

ifstream fin(InFile);
ofstream fout(OutFile);

struct TrieNode
{
	TrieNode()
	{
		child[0]=child[1]=NULL;
		start=0;
	}

	int start;
	TrieNode *child[2];
};

int N,A,CurrXOR,CurrIndex,Sol=-1,SolEnd,SolStart,Array[MaxN],BestXOR,BestStart;
TrieNode root;

inline void MakeArray(int A)
{
	for(register int i=20;i>=0;--i)
	{
		Array[i]=A&1;
		A>>=1;
	}
}

inline int NOT(const int &A)
{
	if(A==0)
	{
		return 1;
	}
	return 0;
}

void TrieSearch(TrieNode *node, int index=0)
{
	if(index==21)
	{	
		BestStart=node->start;
		return;
	}
	
	
	if(node->child[NOT(Array[index])])
	{
		BestXOR<<=1;
		BestXOR+=NOT(Array[index]);
		TrieSearch(node->child[NOT(Array[index])],index+1);
	}
	else
	{
		BestXOR<<=1;
		BestXOR+=Array[index];
		TrieSearch(node->child[Array[index]],index+1);
	}
}

void TrieAdd(TrieNode *node, int index=0)
{
	if(index==21)
	{
		node->start=CurrIndex;
		return;
	}

	if(!node->child[Array[index]])
	{
		node->child[Array[index]]=new TrieNode;
	}
	TrieAdd(node->child[Array[index]],index+1);
}

int main()
{
	fin>>N;
	CurrIndex=0;
	MakeArray(0);
	TrieAdd(&root);
	for(register int i=1;i<=N;++i)
	{
		CurrIndex=i;
		fin>>A;
		CurrXOR^=A;
		
		MakeArray(CurrXOR);
		BestXOR=0;
		TrieSearch(&root);

		PRINT(CurrXOR<<" "<<BestXOR);
	PRINT(Sol<<" "<<(CurrXOR^BestXOR));


		if((CurrXOR^BestXOR)>Sol)
		{
			PRINT("UPDATE");
			Sol=CurrXOR^BestXOR;
			SolStart=BestStart+1;
			SolEnd=i;
		}

		TrieAdd(&root);
	}
	fin.close();
	
	fout<<Sol<<" "<<SolStart<<" "<<SolEnd;
	fout.close();
	return 0;
}