Submission #1258224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258224		hawashra	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	831 ms	23392 KiB

jobs

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

using vi = vector<int>;

int n, d, m;
vector<int> a;               // availability of each job (1‑based)
vector<vi> answer;           // answer[day] = list of jobs on that day

/*------------------------------------------------------------
   Check if we can schedule all jobs with at most `machines`
   parallel jobs per day.
   If `fill` is true, the global vector `answer` is filled with
   a concrete schedule.
   ------------------------------------------------------------*/
bool feasible(int machines, bool fill = false) {
    // release[day] = ids of jobs that become available on this day
    vector<vector<int>> release(n + 2);
    for (int i = 0; i < m; ++i) {
        if (a[i] > n) return false;                // impossible input
        release[a[i]].push_back(i);
    }

    // (deadline, job_id)  –  smallest deadline on top
    using pii = pair<int,int>;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    if (fill) answer.assign(n + 1, {});

    for (int day = 1; day <= n; ++day) {
        // new jobs become available
        for (int id : release[day]) {
            int deadline = a[id] + d;
            if (deadline > n) deadline = n;   // days after n are useless
            pq.emplace(deadline, id);
        }

        int slots = machines;
        while (slots && !pq.empty()) {
            auto [deadline, id] = pq.top(); pq.pop();
            if (deadline < day) return false;  // missed its last possible day
            if (fill) answer[day].push_back(id + 1); // store 1‑based id
            --slots;
        }
    }
    // after day n there must be no remaining jobs
    return pq.empty();
}

/*------------------------------------------------------------*/

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

    if(!(cin >> n >> d >> m)) return 0;
    a.resize(m);
    for (int i = 0; i < m; ++i) cin >> a[i];

    int lo = 1, hi = m, best = m;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (feasible(mid)) {
            best = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    // build the concrete schedule for the optimal number of machines
    feasible(best, true);

    cout << best << '\n';
    for (int day = 1; day <= n; ++day) {
        for (int id : answer[day]) cout << id << ' ';
        cout << "0\n";
    }
    return 0;
}

• Subtask 1: 100 / 100