Cod sursa(job #1492145)

Utilizator nickulNic Kul nickul Data 27 septembrie 2015 07:30:39
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 kb
#include<fstream>
#include<vector>
#include<map>

using namespace std;

vector<size_t> gol;

struct nod
{
	size_t zero,unu;
};
vector<nod> noduri;

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

struct triplet
{
	triplet():unu(0),doi(0),trei(0){}
	triplet(size_t u, size_t d, size_t t):unu(u),doi(d),trei(t){}
	triplet(size_t u, size_t d):unu(u),doi(d),trei(fr[u].val^fr[d].val){}
	size_t unu,doi,trei;
};
vector<triplet> sol;


void rez(size_t zero, size_t unu)
{
	bool ok=0;
	vector<size_t> z,u;
	if(fr.count(zero)&&fr.count(unu))
	{
		sol.push_back(triplet(unu,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;
	}
	fr[21].poz.push_back(0);
	fr[21].val=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))
		{
			fr[poz].poz.push_back(i);
		}
		else
		{
			frunza f;
			f.poz.push_back(i);
			f.val=y;
			fr.emplace(poz,f);
		}
	}
	rez(0,0);
	for(i=0;i<sol.size();i++)
	{
		if(max<sol[i].trei)
		{
			max=sol[i].trei;
			sol.erase(sol.begin(),sol.begin()+i);
			i=0;
		}
		if(max>sol[i].trei)
		{
			sol.erase(sol.begin()+i);
			i--;
		}
	}
	out<<max<<' ';
	size_t start=n,stop=n,min1,min2;
	for(k=0;k<sol.size();k++)
	{
		min1=fr[sol[k].unu].poz[0];
		min2=fr[sol[k].doi].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<fr[sol[k].doi].poz.size();i++)
				{
					if(fr[sol[k].doi].poz[i]>=min2) break;
					start=fr[sol[k].doi].poz[i];
				}
			}
			else
			{
				for(i=1;i<fr[sol[k].unu].poz.size();i++)
				{
					if(fr[sol[k].unu].poz[i]>=min2) break;
					start=fr[sol[k].unu].poz[i];
				}
			}
		}
	}
	out<<start+1<<' '<<((stop)?stop:stop+1);
}