Cod sursa(job #938546)

Utilizator Kira96Denis Mita Kira96 Data 12 aprilie 2013 20:55:03
Problema Fractal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<fstream>
#include<vector>
#define DIM 260
using namespace std;
ifstream f("hogwarts.in");
ofstream g("hogwarts.out");
void write(),solve();
struct E{int n,po;}l[DIM];
struct e{int n,c;}vr[DIM];
vector<int> v[DIM];
int cm(e A,e B){return A.c>B.c;}
int cm2(E A,E B){return A.n<B.n;}
int n,k,m,i,p,lp,S,j,t;
bool viz[DIM];
int main ()
{
	f>>n>>m>>k;
	for(i=1;i<=m;++i)
	{
		f>>l[i].n;
		S+=l[i].n;
		l[i].po=i;
	}
	for(i=1;i<=k;++i)
	{
		f>>vr[1].n;
		viz[vr[1].n]=1;
	}
	n-=k;
	for(i=1;i<=n;++i)
	{
		f>>vr[++t].n>>vr[t].c;
		if(!vr[t].n)
		{
			t--;
			break;
		}
		vr[t].c++;
		S-=vr[t].c;
		viz[vr[t].n]=1;
	}
	n+=k;
	for(i=1;i<=n;++i)
		if(!viz[i])
		{
			++t;
			S--;
			vr[t].c=1;
			vr[t].n=i;
			viz[i]=1;
		}
	n-=k;
	sort(l+1,l+m+1,cm2);
	sort(vr+1,vr+n+1,cm);
	solve();
	write();
	return 0;
}
void solve()
{
	for(i=1;i<=vr[1].c;++i)
	{
		v[i].push_back(vr[1].n);
		l[i].n--;
	}
	p=1;
	lp=i-1;
	while(!l[p].n)
		p++;
	for(i=2;i<=n;++i)
	{

		if(p+vr[i].c-1>=lp)
		{
			for(j=p;vr[i].c;++j)
			{
				v[j].push_back(vr[i].n);
				l[j].n--;
				vr[i].c--;
			}
			if(!l[lp].n)
			break;
			while(l[p].n==0)
				p++;
		}
		else
		{
			while(p+vr[i].c-1<lp&&S)
			{
				S--;
				p++;
			}
			if(p+vr[i].c-1!=lp)
				lp=p+vr[i].c-1;
			for(j=p;vr[i].c;++j)
			{
				v[j].push_back(vr[i].n);
				l[j].n--;
				vr[i].c--;
			}
			if(!l[lp].n)
			break;
			while(l[p].n==0)
				p++;
		}

	}
	i++;
	p=lp;
	for(;i<=n;++i)
	{
		while(l[p].n==0&&p<=m)
			p++;
		if(p>m)
		{
			p=lp-1;
			lp--;
		}
		for(j=p;vr[i].c&&j<=m;++j)
		{
			if(l[j].n)
			{
			v[j].push_back(vr[i].n);
			l[j].n--;
			vr[i].c--;
			}
		}
		if(vr[i].c)
			i--;
	}
}
void write()
{
	p=1;
	for(p=1;p<=m;++p)
	{
		for(j=1;j<=m;++j)
			if(l[j].po==p)
			{
				for(t=0;t<v[j].size();++t)
					g<<v[j][t]<<" ";
				g<<"\n";
				break;
			}
	}
	g<<lp<<"\n";
	for(i=1;i<=lp;++i)
	{
		for(t=0;t<v[i].size();++t)
			g<<v[i][t]<<" ";
		g<<"\n";
	}
}