Cod sursa(job #586101)

Utilizator ChallengeMurtaza Alexandru Challenge Data 30 aprilie 2011 13:42:41
Problema Avioane Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 3.17 kb
#include <fstream>
#include <set>

using namespace std;

const char InFile[]="fabrica.in";
const char OutFile[]="fabrica.out";
const int MaxNA=50111;
const int MaxNB=50111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct proc
{
	proc(int _t=0, int _p=0):t(_t),p(_p){}
	int t,p;
};

bool operator< (const proc &a, const proc &b)
{
	return a.t<b.t;
}

int N,NA,NB,VA[MaxNA],VB[MaxNB],solA,solAB;
multiset<int> freeA;
multiset<proc> runA;
multiset<int> freeB;
multiset<proc> runB;

inline bool goodA(int val)
{
	freeA.clear();
	runA.clear();
	for(register int i=1;i<=NA;++i)
	{
		freeA.insert(VA[i]);
	}
	int n=N;
	int t=0;
	while(n)
	{
		bool ok=false;
		while(!freeA.empty() && n)
		{
			int p=(*freeA.begin());
			if(t+p>val)
			{
				break;
			}
			ok=true;
			--n;
			runA.insert(proc(t+p,p));
			freeA.erase(freeA.begin());
		}
		if(!runA.empty())
		{
			t=runA.begin()->t;
			while(!runA.empty())
			{
				if((*runA.begin()).t>t)
				{
					break;
				}
				ok=true;
				freeA.insert(runA.begin()->p);
				runA.erase(runA.begin());
			}
		}
		if(!ok)
		{
			break;
		}
	}
	return !n;
}

inline bool goodAB(int val)
{
	freeA.clear();
	runA.clear();
	for(register int i=1;i<=NA;++i)
	{
		freeA.insert(VA[i]);
	}
	freeB.clear();
	runB.clear();
	for(register int i=1;i<=NB;++i)
	{
		freeB.insert(VB[i]);
	}
	int nA=N;
	int nB=N;
	int t=0;
	int x=0;
	while(nB)
	{
		bool ok=false;
		while(!freeA.empty() && nA)
		{
			int p=(*freeA.begin());
			if(t+p>val)
			{
				break;
			}
			ok=true;
			--nA;
			runA.insert(proc(t+p,p));
			freeA.erase(freeA.begin());
		}
		while(!freeB.empty())
		{
			multiset<int>::iterator it=freeB.end();
			--it;
			if(t+*it<=val)
			{
				break;
			}
			freeB.erase(*it);
		}
		while(x)
		{
			if(freeB.empty())
			{
				break;
			}
			multiset<int>::iterator it=freeB.end();
			--it;
			int p=*it;
			if(t+p>val)
			{
				break;
			}
			ok=true;
			--nB;
			runB.insert(proc(t+p,p));
			freeB.erase(it);
			--x;
		}
		int tp=2147483647;
		if(!runA.empty())
		{
			tp=runA.begin()->t;
		}
		if(!runB.empty())
		{
			if(runB.begin()->t<tp)
			{
				tp=runB.begin()->t;
			}
		}
		t=tp;
		while(!runA.empty())
		{
			if((*runA.begin()).t>t)
			{
				break;
			}
			ok=true;
			++x;
			freeA.insert(runA.begin()->p);
			runA.erase(runA.begin());
		}
		while(!runB.empty())
		{
			if((*runB.begin()).t>t)
			{
				break;
			}
			ok=true;
			freeB.insert(runB.begin()->p);
			runB.erase(runB.begin());
		}
		
		if(!ok)
		{
			break;
		}
	}
	return !nB;
}

int main()
{
	fin>>N>>NA>>NB;
	for(register int i=1;i<=NA;++i)
	{
		fin>>VA[i];
	}
	for(register int i=1;i<=NB;++i)
	{
		fin>>VB[i];	
	}
	fin.close();

	int st=0;
	int dr=2147483647;
	
	while(st<=dr)
	{
		int mid=st+((dr-st)>>1);
		if(goodA(mid))
		{
			dr=mid-1;
			solA=mid;
		}
		else
		{
			st=mid+1;
		}
	}

	st=0;
	dr=2147483647;
	
	while(st<=dr)
	{
		int mid=st+((dr-st)>>1);
		if(goodAB(mid))
		{
			dr=mid-1;
			solAB=mid;
		}
		else
		{
			st=mid+1;
		}
	}

	fout<<solA<<" "<<solAB<<"\n";
	fout.close();
	return 0;
}