Submission #912596

#	Time	Username	Problem	Language	Result	Execution time	Memory
912596		randomlurker	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	1080 ms	65536 KiB

jobs

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
using namespace std;

int n, d, m;
priority_queue<int, vector<int>, greater<>> reqs;
priority_queue<int, vector<int>, greater<>> reqsCopy;
priority_queue<int, vector<int>, greater<>> pq;
map<int, queue<int>> locs;

bool test(int x){
    for(int day=reqs.top(); day<n; day++){
        if (empty(pq) and empty(reqs)) break;
        while (!empty(reqs) and reqs.top() <= day) {
            pq.push(reqs.top() + d);
            reqs.pop();
        }
        for(int i=0; i<x; i++){
            // Complete the x tasks that are due soonest. If any are overdue, then return false
            if (day > pq.top()) return false;
            else pq.pop();
            if (empty(pq)) break;
        }
    }
    return (empty(pq));
}

int main() {
    cin >> n >> d >> m;
    int x;
    for(int i=1; i<=n; i++){
        locs.insert({i, {}});
    }
    for(int i=0; i<m; i++){
        cin >> x;
        reqs.push(x);
        locs[x].push(i+1);
    }
    int lo = 1;
    int hi = INT_MAX;
    int mid;
    reqsCopy = priority_queue<int, vector<int>, greater<>> (reqs);
    while(lo < hi){
        reqs = priority_queue<int, vector<int>, greater<>> (reqsCopy);
        pq = {};
        mid = lo + (hi-lo)/2;
        if (test(mid)){
            hi = mid;
        }
        else lo = mid+1;
    }
    cout << lo << endl;

    // Print out optimal movements
    reqs = priority_queue<int, vector<int>, greater<>> (reqsCopy);
    pq = {};
    string dayOut;
    for(int day=1; day<=n; day++){
        dayOut = "";
        while (!empty(reqs) and reqs.top() <= day) {
            pq.push(reqs.top() + d);
            reqs.pop();
        }
        for(int i=0; i<lo; i++){
            if (empty(pq)) break;
            else{
                int goodIdx = locs[pq.top()-d].front();
                locs[pq.top()-d].pop();
                dayOut += to_string(goodIdx) + " ";
                pq.pop();
            }
        }
        dayOut += "0";
        cout << dayOut << endl;
    }
    return 0;
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
 */

• Subtask 1: 45 / 100