Cod sursa(job #648813)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 14 decembrie 2011 17:13:51
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<fstream>
using namespace std;
int n,v[100010],sumaxor[100010],sol=-1,st,dr,lim=22;
struct Trie
{
	Trie *st,*dr;
	int poz;
	Trie()
	{
		poz=0;
		st=dr=0;
	}
};
Trie *T=new Trie;

inline int Search(Trie *nod,int x)
{
	int i,bit;
	for(i=lim;i>=0;i--)
	{
		bit=(x & (1<<i));
		if(bit)				//bitul=1 , deci merg in nodul cu bitul 0 ca sa maximizez suma xor
		{
			if(nod->dr!=0)
				nod=nod->dr;
			else
				nod=nod->st;
		}
		else				//bitul=0 , deci merg in nodul cu bitul 1 ca sa maximizez suma xor
		{
			if(nod->st!=0)
				nod=nod->st;
			else
				nod=nod->dr;
		}
	}
	return nod->poz;	//returnez indicele elementului gasit
}

inline void Push(Trie *nod,int x,int poz)
{
	int i,bit;
	for(i=lim;i>=0;i--)
	{
		bit=(x & (1<<i));
		if(bit)						//bitul=1 , deci merg in nodul cu bitul 1
		{
			if(nod->st==0)
				nod->st=new Trie;
			nod=nod->st;
		}
		else						//bitul=1 , deci merg in nodul cu bitul 1
		{
			if(nod->dr==0)
				nod->dr=new Trie;
			nod=nod->dr;
		}
	}
	nod->poz=poz;	//am ajuns la pozitia corecta si inserez indicele elementului
}

int main()
{
	int i,j;
	ifstream fin("xormax.in");
	fin>>n;
	Push(T,0,0);
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
		sumaxor[i]=(sumaxor[i-1]^v[i]);
		j=Search(T,sumaxor[i]);	//caut j<i astfel incat suma xor de la j+1 la i sa fie maxima
		if(sol<(sumaxor[j]^sumaxor[i]))		//actualizez maximul
		{
			sol=(sumaxor[j]^sumaxor[i]);
			st=j;
			dr=i;
		}
		Push(T,sumaxor[i],i);		//introduc noua suma partiala in Trie
	}
	fin.close();
	ofstream fout("xormax.out");
	fout<<sol<<' '<<(st+1)<<' '<<dr<<"\n";
	fout.close();
	return 0;
}