Cod sursa(job #585689)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 30 aprilie 2011 11:04:58
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Open Marime 3.38 kb
#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;
}