A171746 题解

不会做的看这边~

#include <bits/stdc++.h>
using namespace std;

enum JobStatus {
    WAITING = 0,
    CANCELLED = -1,
    PRINTING = -2,
    COMPLETED = -3
};

struct Printer {
    int id;
    long long speed;
    bool paused;
    int current_job_id;
    long long finish_time;

    Printer() : id(0), speed(0), paused(false), current_job_id(0), finish_time(0) {}
    Printer(int _id, long long _speed) : id(_id), speed(_speed), paused(false), current_job_id(0), finish_time(0) {}
};

struct Operation {
    long long t;
    int op;
    int x;
};

struct Event {
    long long time;
    int printer_id;
    bool operator>(const Event& other) const {
        return time > other.time;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int p, q;
    if (!(cin >> p >> q)) return 0;

    vector<Printer> printers(p + 1);
    for (int i = 1; i <= p; ++i) {
        long long s;
        cin >> s;
        printers[i] = Printer(i, s);
    }

    vector<Operation> ops(q);
    for (int i = 0; i < q; ++i) {
        cin >> ops[i].t >> ops[i].op >> ops[i].x;
    }

    vector<long long> results; 
    results.push_back(0);
    
    vector<int> job_status;
    job_status.push_back(0);

    queue<int> wait_queue;
    priority_queue<Event, vector<Event>, greater<Event>> completion_events;

    int next_job_id = 1;

    vector<int> job_pages;
    job_pages.push_back(0);

    int idx = 0;
    
    while (idx < q || !completion_events.empty()) {
        
        long long next_op_time = (idx < q) ? ops[idx].t : LLONG_MAX;
        long long next_event_time = completion_events.empty() ? LLONG_MAX : completion_events.top().time;
        
        long long current_t;
        bool has_ops_at_current_t = false;
        
        if (idx < q && ops[idx].t <= next_event_time) {
            current_t = ops[idx].t;
            has_ops_at_current_t = true;
        } else if (!completion_events.empty()) {
            current_t = next_event_time;
            has_ops_at_current_t = false;
        } else {
            break;
        }
        
        while (!completion_events.empty() && completion_events.top().time == current_t) {
            int pid = completion_events.top().printer_id;
            completion_events.pop();
            
            Printer& pr = printers[pid];
            if (pr.current_job_id != 0 && pr.finish_time == current_t) {
                int jid = pr.current_job_id;
                results[jid] = current_t;
                job_status[jid] = 1;
                
                pr.current_job_id = 0;
                pr.finish_time = 0;
            }
        }
        
        if (has_ops_at_current_t) {
            while (idx < q && ops[idx].t == current_t) {
                int op = ops[idx].op;
                int x = ops[idx].x;
                
                if (op == 1) {
                    int pages = x;
                    int jid = next_job_id++;
                    
                    job_pages.push_back(pages);
                    job_status.push_back(-2);
                    results.push_back(-2);
                    
                    wait_queue.push(jid);
                } else if (op == 2) {
                    int jid = x;
                    if (jid < job_status.size() && job_status[jid] == -2) {
                        job_status[jid] = -1;
                        results[jid] = -1;
                    }
                } else if (op == 3) {
                    if (x >= 1 && x <= p) {
                        printers[x].paused = true;
                    }
                } else if (op == 4) {
                    if (x >= 1 && x <= p) {
                        printers[x].paused = false;
                    }
                }
                
                idx++;
            }
        }
        
        while (true) {
            int avail_pid = -1;
            for (int i = 1; i <= p; ++i) {
                if (printers[i].current_job_id == 0 && !printers[i].paused) {
                    avail_pid = i;
                    break;
                }
            }
            
            if (avail_pid == -1) break;
            
            int assign_jid = -1;
            while (!wait_queue.empty()) {
                int jid = wait_queue.front();
                if (job_status[jid] == -1) {
                    wait_queue.pop();
                } else if (job_status[jid] == -2) {
                    wait_queue.pop();
                    assign_jid = jid;
                    break;
                } else {
                    wait_queue.pop();
                }
            }
            
            if (assign_jid == -1) break;
            
            Printer& pr = printers[avail_pid];
            pr.current_job_id = assign_jid;
            job_status[assign_jid] = -3;
            
            long long duration = (long long)job_pages[assign_jid] * pr.speed;
            pr.finish_time = current_t + duration;
            
            completion_events.push({pr.finish_time, avail_pid});
        }
    }
    
    for (int i = 1; i < next_job_id; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}