Pagini recente » Cod sursa (job #2296699) | Cod sursa (job #1907111) | Cod sursa (job #2103959) | Cod sursa (job #1650729) | Cod sursa (job #1758197)
#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;
}