Cod sursa(job #95280)

Utilizator piroslPiros Lucian pirosl Data 28 octombrie 2007 00:48:05
Problema Xor Max Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <iostream>
#include <fstream>
using namespace std;

const int maxl = 22;

class nod
{
public:
	nod(bool leaf);
	~nod();
	char* binValue;
	int value;
	int poz;
	class nod *left;
	class nod *rigth;

	void setValue(int v);
};

nod::nod(bool leaf)
{
	if(leaf)
	{
		binValue = new char[maxl];
		for(int i=0;i<maxl;++i)
			binValue[i] = 0;
	}
	else
	{
		binValue = 0;
	}
	left = 0;
	rigth = 0;
}

nod::~nod()
{
	if(binValue != 0 )
		delete[] binValue;
	if(left != 0 )
		delete left;
	if(rigth != 0 )
		delete rigth;
}

void nod::setValue(int v)
{
	value = v;
	int poz = maxl - 1;
	while(v > 0)
	{
		binValue[poz--] = v%2;
		v /= 2;
	}
}

void add(class nod *toNod, class nod *newNod, int level, bool left)
{
	if(level == maxl-1) 
	{
		if(left) 
		{		
			toNod->left = newNod;
		}
		else
			toNod->rigth = newNod;
	}
	if(newNod->binValue[level] == 0) 
	{
		if(toNod->left == 0)
		{
			class nod *leftNod = new nod(false);
			toNod->left = leftNod;
		}
		add(toNod->left, newNod, level+1, true);
	}
	if(newNod->binValue[level] == 1) 
	{
		if(toNod->rigth == 0)
		{
			class nod *rigthNod = new nod(false);
			toNod->rigth = rigthNod;
		}
		add(toNod->rigth, newNod, level+1, false);
	}
}

nod* getMax(class nod *fromNod, class nod *vNod, int level)
{
	if(fromNod == 0)
		return 0;
	
	if(level == maxl-1)
	{
		if(vNod->binValue[level] == 0) 
		{
			if(fromNod->rigth != 0)
				return fromNod->rigth;
			else
			{
				if(fromNod->left != 0)
					return fromNod->left;
				else
					return 0;
			}
		}
		if(vNod->binValue[level] == 1) 
		{
			if(fromNod->left != 0)
				return fromNod->left;
			else
			{
				if(fromNod->rigth != 0)
					return fromNod->rigth;
				else
					return 0;
			}
		}
	}

	if(vNod->binValue[level] == 0) 
	{
		if(fromNod->rigth != 0)
			return getMax(fromNod->rigth, vNod, level+1);
		else
		{
			if(fromNod->left != 0)
				return getMax(fromNod->left, vNod, level+1);
			else
				return 0;
		}
	}
	if(vNod->binValue[level] == 1) 
	{
		if(fromNod->left != 0)
			return getMax(fromNod->left, vNod, level+1);
		else
		{
			if(fromNod->rigth != 0)
				return getMax(fromNod->rigth, vNod, level+1);
			else
				return 0;
		}
	}
}

int main(void)
{
	ifstream in;
	ofstream out;
	in.open("xormax.in");
	out.open("xormax.out");
	int n;
	in >> n;
	int xorV = 0;
	int maxV = 0;
	int s = 0;
	int e = 0;
	class nod* tree = new nod(false);

	for(int i=0;i<n;++i)
	{
		int d;
		in >> d;
		xorV = xorV ^ d;
		if(d > maxV) 
		{
			maxV = d;
			s = i;
			e = i;
		}
		class nod *n = new nod(true);
		n->setValue(xorV);
		n->poz = i;
		class nod* maxValue = getMax(tree, n, 0);
		if(maxValue != 0) 
		{
			int tmpV = maxValue->value ^ xorV;
			if(tmpV > maxV)
			{
				maxV = tmpV;
				s = maxValue->poz+1;
				e = i;
			}
		}
		add(tree, n, 0, true);
	}
	in.close();
	out << maxV << " " << s+1 << " " << e+1 << endl;
	out.close();
//	delete tree;
	return 0;
}