Cod sursa(job #586205)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 30 aprilie 2011 14:05:37
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 2.27 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream f("fabrica.in");
ofstream g("fabrica.out");

struct procesor{
    unsigned long long dur;
};
struct procesor2{
    unsigned long long dur;
    unsigned long long unt;
};
struct compara{
    bool operator()(const procesor& x, const procesor& y) const {
         return (x.dur > y.dur);
  }
};
struct compara2{
    bool operator()(const procesor2& x, const procesor2& y) const {
         if (x.unt==y.unt) return (x.dur > y.dur);
         else return (x.unt > y.unt);
  }
};
priority_queue<procesor, vector<procesor>, compara> qa;
priority_queue<procesor2, vector<procesor2>, compara2> qa2;
priority_queue<procesor, vector<procesor>, compara> qb;
priority_queue<procesor2, vector<procesor2>, compara2> qb2;

unsigned long long n,i,nra,nrb,d,nrv,tt,ta,n2,nrta,nrtb,pb;
procesor p;
procesor2 p2;
bool stop;
int main () {
    f >> n >> nra >> nrb;
    p.dur=4294967295;
    qa.push(p);
    qb.push(p);
    for (i=1;i<=nra;i++) {
        f >> d;
        p.dur=d;
        qa.push(p);
    }
    for (i=1;i<=nrb;i++) {
        f >> d;
        p.dur=d;
        qb.push(p);
    }
    p2.dur=p2.unt=4294967295;
    qa2.push(p2);
    qb2.push(p2);
    tt=ta=0;n2=n;
    while (n2>0) {
        tt++;pb=0;
        p2=qa2.top();
        while (p2.unt<=tt) {
            p.dur=p2.dur;qa.push(p);qa2.pop();p2=qa2.top();pb++;
        }
        stop=false;
        while (qa.empty()==false && stop==false && nrta<n){
            p=qa.top();p2=qa2.top();
            if (p.dur+tt<=p2.unt) {
                qa.pop();p2.dur=p.dur;p2.unt=tt+p2.dur;qa2.push(p2);nrta++;
            }
            else stop=true;
        }
        if (nrta==n) {ta=tt;nrta+=n;}
        p2=qb2.top();
        while (p2.unt<=tt) {
            p.dur=p2.dur;qb.push(p);qb2.pop();p2=qb2.top();
        }
        stop=false;
        while (qb.empty()==false && stop==false && pb>0 && nrtb<n) {
            p=qb.top();p2=qb2.top();
            if (p.dur+tt<=p2.unt) {
                qb.pop();p2.dur=p.dur;p2.unt=tt+p2.dur;qb2.push(p2);nrtb++;pb--;
            }
            else stop=true;
        }
        if (nrtb==n) n2=0;
    }
    g << ta << ' ' <<tt << '\n';
    f.close();g.close();
    return 0;
}