Cod sursa(job #1758197)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 16 septembrie 2016 19:22:11
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <functional>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define NMAX 100010
#define PMAX 50000

class ProcessorList
{
public:

	int nr, nrAvailable;
	int t[PMAX];
	pii list[PMAX];

	void init()
	{
		nrAvailable = nr;

		for (int i = 0; i < nr; ++i) list[i] = {t[i], i};
		make_heap(list, list + nrAvailable, greater<pii>());
	}

	int getProcessor()
	{
		if (nrAvailable == 0) return -1;

		int proc = list[0].second;
		pop_heap(list, list + nrAvailable, greater<pii>()); --nrAvailable;

		return proc;
	}

	void newProcessor(int proc)
	{
		list[nrAvailable++] = {t[proc], proc};
		push_heap(list, list + nrAvailable, greater<pii>());
	}

	bool hasAvailable()
	{
		return nrAvailable > 0;
	}
};

int top;
pii v[NMAX];
ProcessorList A, B;

void push(int, int);
pii pop();

int main()
{
	int i, n, waitingForA, waitingForB, terminatedA, terminatedB, timeA, timeB, proc;
	ifstream fin("fabrica.in");
	ofstream fout("fabrica.out");

	fin >> n >> A.nr >> B.nr;
	for (i = 0; i < A.nr; ++i) fin >> A.t[i];
	for (i = 0; i < B.nr; ++i) fin >> B.t[i];

	A.init();
	B.init();

	waitingForA = n;
	waitingForB = 0;
	terminatedA = terminatedB = 0;
	for (top = 0, i = 1; terminatedA < n || terminatedB < n; ++i)
	{
		if (A.hasAvailable() && waitingForA > 0)
		{
			proc = A.getProcessor();

			push(A.t[proc], proc);
			--waitingForA;
		}
		else
		{
			auto aux = pop();

			if (aux.second < A.nr) // process A terminated
			{
				if (++terminatedA == n) timeA = aux.first;

				if (waitingForA)
				{
					proc = A.getProcessor();

					push(aux.first + A.t[proc], proc);
					--waitingForA;
				}

				if (B.hasAvailable())
				{
					proc = B.getProcessor();

					push(aux.first + B.t[proc], A.nr + proc);
				}
				else ++waitingForB;
			}
			else // process b terminated
			{
				if (++terminatedB == n) timeB = aux.first;

				if (waitingForB)
				{
					proc = B.getProcessor();

					push(aux.first + B.t[proc], A.nr + proc);
					--waitingForB;
				}
			}
		}
	}

	fout << timeA << ' ' << timeB << '\n';

	fin.close();
	fout.close();

	return 0;
}


void push(int time, int proc)
{
	v[top++] = {time, proc};
	push_heap(v, v + top, greater<pii>());
}

pii pop()
{
	pii aux = v[0];

	pop_heap(v, v + top, greater<pii>()); --top;

	if (aux.second < A.nr) A.newProcessor(aux.second);
	else B.newProcessor(aux.second - A.nr);

	return aux;
}