Cod sursa(job #1490914)

Utilizator nickulNic Kul nickul Data 24 septembrie 2015 14:13:08
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include<fstream>
#include<vector>

using namespace std;

struct nod
{
	bool fr;
	size_t zero,unu,val;
	vector<size_t> poz;
};

vector<nod> noduri;
vector<size_t> st,dr;

void rez(size_t zero, size_t unu)
{
	bool ok=0;
	vector<size_t> z,u;
	if(!noduri[zero].fr&&!noduri[unu].fr)
	{
		st.push_back(unu);
		dr.push_back(zero);
		return;
	}
	if(zero==unu)
	{
		if(noduri[zero].zero)
		{
			if(noduri[zero].unu)
			{
				rez(noduri[zero].zero,noduri[zero].unu);
				return;
			}
			rez(noduri[zero].zero,noduri[zero].zero);
			return;
		}
		if(noduri[zero].unu)
		{
			rez(noduri[zero].unu,noduri[zero].unu);
			return;
		}
	}
	if(noduri[zero].zero&&noduri[unu].unu)
	{
		rez(noduri[zero].zero,noduri[unu].unu);
		ok=1;
	}
	if(noduri[zero].unu&&noduri[unu].zero)
	{
		rez(noduri[zero].unu,noduri[unu].zero);
		ok=1;
	}
	if(ok) return;
	if(noduri[zero].zero&&noduri[unu].zero)
		rez(noduri[zero].zero,noduri[unu].zero);
	if(noduri[zero].unu&&noduri[unu].unu)
		rez(noduri[zero].unu,noduri[unu].unu);
	return;
}

ifstream in("xormax.in");
ofstream out("xormax.out");

int main()
{	
	size_t n,x,y=0,i,j,k,poz=0,max=0;
	noduri.resize(1);
	noduri[0].zero=0;
	noduri[0].unu=0;	
	for(k=21;k>0;k--)
	{
		noduri.resize(noduri.size()+1);
		noduri[poz].zero=noduri.size()-1;
		noduri[noduri.size()-1].unu=0;
		noduri[noduri.size()-1].zero=0;
		poz=noduri[poz].zero;
	}
	noduri[poz].poz.push_back(0);
	noduri[poz].val=0;
	noduri[poz].fr=false;
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>x;
		y^=x;
		x=y;
		j=0;
		poz=0;
		while(x>>j) j++;
		for(k=21;k>0;k--)
		{
			if(x&1<<(k-1))
			{
				if(!noduri[poz].unu)
				{
					noduri.resize(noduri.size()+1);
					noduri[poz].unu=noduri.size()-1;
					noduri[noduri.size()-1].unu=0;
					noduri[noduri.size()-1].zero=0;
				}
				poz=noduri[poz].unu;
			}
			else
			{
				if(!noduri[poz].zero)
				{
					noduri.resize(noduri.size()+1);
					noduri[poz].zero=noduri.size()-1;
					noduri[noduri.size()-1].unu=0;
					noduri[noduri.size()-1].zero=0;
				}
				poz=noduri[poz].zero;
			}
		}
		noduri[poz].poz.push_back(i);
		noduri[poz].val=x;
		noduri[poz].fr=false;
	}
	rez(0,0);
	for(i=0;i<st.size();i++)
	{
		if(max<(noduri[st[i]].val^noduri[dr[i]].val))
		{
			max=noduri[st[i]].val^noduri[dr[i]].val;
			st.erase(st.begin(),st.begin()+i);
			dr.erase(dr.begin(),dr.begin()+i);
			i=0;
		}
		if(max>(noduri[st[i]].val^noduri[dr[i]].val))
		{
			st.erase(st.begin()+i);
			dr.erase(dr.begin()+i);
			i--;
		}
	}
	out<<max<<' ';
	size_t start=1,stop=1,min1,min2;
	nod s,d;
	s=noduri[st[0]];
	d=noduri[dr[0]];
	noduri.clear();
	noduri.shrink_to_fit();
	min1=s.poz[0];
	min2=d.poz[0];
	for(i=1;i<s.poz.size();i++)
	{
		if(s.poz[i]<min1) min1=s.poz[i];
	}
	for(i=1;i<d.poz.size();i++)
	{
		if(d.poz[i]<min2) min2=d.poz[i];
	}
	if(min1<min2)
	{
		/*stop=min2;
		for(i=0;i<s.poz.size();i++)
		{
			if(s.poz[i]>min1&&s.poz[i]<min2) min1=s.poz[i];
		}
		start=min1+1;*/
	}
	else
	{
		/*stop=min1;
		for(i=0;i<d.poz.size();i++)
		{
			if(d.poz[i]>min2&&d.poz[i]<min1) min2=d.poz[i];
		}
		start=min2+1;*/
	}
	out<<min1+1<<' '<<min2;
}