Cod sursa(job #1492141)

Utilizator nickulNic Kul nickul Data 27 septembrie 2015 06:36:08
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include<fstream>
#include<vector>
#include<map>

	using namespace std;

struct nod
{
	size_t zero,unu;
};

struct frunza
{
	size_t val,nod;
	vector<size_t> poz;
};

vector<nod> noduri;
vector<size_t> st,dr;
map<size_t,size_t> fr;
vector<frunza> frunze;

void rez(size_t zero, size_t unu)
{
	bool ok=0;
	vector<size_t> z,u;
	if(fr.count(zero)&&fr.count(unu))
	{
		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);
		poz=noduri[poz].zero=noduri.size()-1;
		noduri[noduri.size()-1].unu=0;
		noduri[noduri.size()-1].zero=0;
	}
	frunze.resize(1);
	frunze[0].poz.push_back(0);
	frunze[0].val=0;
	frunze[0].nod=0;
	fr.emplace(21,0);
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>x;
		y^=x;
		j=0;
		poz=0;
		while(y>>j) j++;
		for(k=21;k>0;k--)
		{
			if(y&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;
			}
		}
		if(fr.count(poz))
		{
			frunze[fr[poz]].poz.push_back(i);
		}
		else
		{
			fr.emplace(poz,frunze.size());
			frunze.resize(frunze.size()+1);
			frunze[frunze.size()-1].poz.push_back(i);
			frunze[frunze.size()-1].val=y;
		}
	}
	rez(0,0);
	for(i=0;i<st.size();i++)
	{
		if(max<(frunze[fr[st[i]]].val^frunze[fr[dr[i]]].val))
		{
			max=frunze[fr[st[i]]].val^frunze[fr[dr[i]]].val;
			st.erase(st.begin(),st.begin()+i);
			dr.erase(dr.begin(),dr.begin()+i);
			i=0;
		}
		if(max>(frunze[fr[st[i]]].val^frunze[fr[dr[i]]].val))
		{
			st.erase(st.begin()+i);
			dr.erase(dr.begin()+i);
			i--;
		}
	}
	out<<max<<' ';
	size_t start=n,stop=n,min1,min2;
	for(k=0;k<st.size()&&k<dr.size();k++)
	{
		min1=frunze[fr[st[k]]].poz[0];
		min2=frunze[fr[dr[k]]].poz[0];
		max=0;
		if (min1>min2) 
		{
			min1^=min2;
			min2^=min1;
			min1^=min2;
			max=1;
		}
		if(min2<stop)
		{
			stop=min2;
			start=min1;
			if(max)
			{
				for(i=1;i<frunze[fr[dr[k]]].poz.size();i++)
				{
					if(frunze[fr[dr[k]]].poz[i]>=min2) break;
					start=frunze[fr[dr[k]]].poz[i];
				}
			}
			else
			{
				for(i=1;i<frunze[fr[st[k]]].poz.size();i++)
				{
					if(frunze[fr[st[k]]].poz[i]>=min2) break;
					start=frunze[fr[st[k]]].poz[i];
				}
			}
		}
	}
	out<<start+1<<' '<<((stop)?stop:stop+1);
}