Pagini recente » Clasament onis-2014-runda-2 | Cod sursa (job #2540490) | Cod sursa (job #2111334) | Cod sursa (job #2540654) | Cod sursa (job #585689)
Cod sursa(job #585689)
#include <stdio.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;
#define NMAX 50100
int ta[NMAX], tb[NMAX], nat[NMAX];
vector<int> r, tfin;
priority_queue<pair<int, int> > pq, pq2;
set<pair<int, int> > next_avail_time;
int i, tcur, Nra, Nrb, N, next_proc, next_finish_time;
void solveA() {
pair<int, int> p;
for (i = 1; i <= Nra; i++)
pq.push(make_pair(-ta[i], i));
while (N--) {
p = pq.top();
r.push_back(-p.first);
pq.pop();
pq.push(make_pair(-(-p.first + ta[p.second]), p.second));
}
}
void solveB() {
set<pair<int, int> >::iterator it;
pair<int, int> p;
// Initialize everything.
while (pq.size() > 0)
pq.pop();
next_avail_time.clear();
tcur = 0;
for (i = 1; i <= Nrb; i++) {
nat[i] = 0;
next_avail_time.insert(make_pair(nat[i], i));
pq.push(make_pair(-tb[i], i));
}
// Process the type B jobs.
N = r.size();
for (i = 0; i < N; i++) {
if (r[i] > tcur) {
p.first = tcur + 1;
p.second = 0;
it = next_avail_time.lower_bound(p);
tcur = r[i];
while (1) {
if (it == next_avail_time.end())
break;
//fprintf(stderr, "old_tcur=%d, new_tcur=%d, (*it).first=%d, (*it).second=%d\n", p.first - 1, tcur, (*it).first, (*it).second);
if ((*it).first > tcur)
break;
pq.push(make_pair(-tb[(*it).second], (*it).second));
it++;
}
}
next_proc = next_finish_time = 0;
while (pq.size() > 0) {
p = pq.top();
if (nat[p.second] <= tcur) {
next_proc = p.second;
next_finish_time = tcur + (-p.first);
break;
} else {
pq.pop();
}
}
while (pq2.size() > 0) {
p = pq2.top();
if ((nat[p.second] > tcur) && (nat[p.second] + tb[p.second] == (-p.first))) {
if ((-p.first) < next_finish_time || !next_proc) {
next_proc = p.second;
next_finish_time = -p.first;
}
break;
} else {
pq2.pop();
}
}
if (nat[next_proc] <= tcur)
pq.pop();
else
pq2.pop();
tfin.push_back(next_finish_time);
next_avail_time.erase(make_pair(nat[next_proc], next_proc));
nat[next_proc] = next_finish_time;
next_avail_time.insert(make_pair(nat[next_proc], next_proc));
if (nat[next_proc] <= tcur) {
pq.push(make_pair(-tb[next_proc], next_proc));
} else {
pq2.push(make_pair(-(nat[next_proc] + tb[next_proc]), next_proc));
}
}
}
int main() {
// Read the input data.
freopen("fabrica.in", "r", stdin);
scanf("%d %d %d", &N, &Nra, &Nrb);
for (i = 1; i <= Nra; i++)
scanf("%d", &ta[i]);
for (i = 1; i <= Nrb; i++)
scanf("%d", &tb[i]);
// Solve A.
solveA();
// Solve B.
solveB();
// Write the output data.
freopen("fabrica.out", "w", stdout);
printf("%d %d\n", r[N - 1], tfin[N - 1]);
return 0;
}