Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
3.8 kB
4
Indexable
Never
#include<iostream>
#include<unordered_map>
#include<queue>
#define MAX_N    105
#define MAX_TOOL 5005
using namespace std;
 
class TOOL {
public:
    int toolidx;
    int stepno;
    int Pt;
    int finishT;
};
TOOL tools[MAX_TOOL];
class cmp {
public:
    bool operator()(int a, int b)const {
        return tools[a].Pt > tools[b].Pt;
    }
};
class cmp2 {
public:
    bool operator()(int x, int y)const {
        if (tools[x].finishT == tools[y].finishT) {
            if (tools[x].stepno == tools[y].stepno) {
                return tools[x].Pt > tools[y].Pt;
            }
            else {
                return tools[x].stepno < tools[y].stepno;
            }
        }
        return tools[x].finishT > tools[y].finishT;
    }
};
priority_queue <int, vector<int>, cmp> stepPq[MAX_N]; //stepwise queue
priority_queue <int, vector<int>, cmp2> timePq;  // all the tools in processing
int n;
 
// for each step
int total[MAX_N];
int waiting[MAX_N];
 
void init(int N) {
    n = N;
    for (int i = 0; i <= N; i++) {
        stepPq[i] = priority_queue<int, vector<int>, cmp>();
         
        //because step is empty at start
        total[i] = waiting[i] = 0;
    }
    timePq = priority_queue<int, vector<int>, cmp2>();
}
 
void setupTool(int T, int stepNo[5000], int procTime[5000]) {
    for (int i = 0; i < T; i++) {
        tools[i].toolidx = i;
        tools[i].stepno = stepNo[i];
        tools[i].Pt = procTime[i];
        tools[i].finishT = 0;
 
        // add tool to priority_queue of step i;
        stepPq[stepNo[i]].push(i);
    }
 
}
void assign_process(int time, int stepno) {
    while (stepPq[stepno].size() != 0 && waiting[stepno] != 0) //priority q has tools and lots are in waiting/standby
    {
        // get min time tool from PQ
        int tool_id = stepPq[stepno].top();
        stepPq[stepno].pop();
         
        // assign this tool
        tools[tool_id].finishT = time + tools[tool_id].Pt;
 
        // update waiting and process_pq
        timePq.push(tool_id);
        waiting[stepno]--;
    }
}
 
void update(int time)
{
    // for updating time
    // time pq has tools in process and finish time of top < current time 
    while (timePq.size() > 0 && tools[timePq.top()].finishT <= time) { 
        // remove from time pq 
        int tool_id = timePq.top();
        timePq.pop();
 
        // add to step pq
        int stepno = tools[tool_id].stepno;
        int current_time = tools[tool_id].finishT;
        total[stepno]--;
 
        if (waiting[stepno] > 0) // a lot is waiting in this step
        {
            // assign this tool to that lot
            // a process finished
             
 
            tools[tool_id].finishT = current_time + tools[tool_id].Pt;
 
            // update waiting and process_pq
            timePq.push(tool_id);
            waiting[stepno]--;
 
 
        }
        else // no waiting => simply add to step PQ
        {
            stepPq[stepno].push(tool_id);
        }
        //move to next step
        stepno++;
        total[stepno]++;
        //updating total and waiting
        if (stepno != n) {
            waiting[stepno]++;
            if (stepPq[stepno].size() > 0) {
                assign_process(current_time, stepno);
            }
        }
    }
 
}
 
void addLot(int time, int number) {
    update(time); // update before adding
    waiting[0] += number;
    total[0] += number;
    assign_process(time,0);
}
 
int simulate(int time, int wip[MAX_N]) {
    update(time); 
    // after update we have updated step priority queue and process pq
    for (int i = 0; i < n; i++) {
        wip[i] = total[i];
    }
 
    return total[n];
}