Submission #1183726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183726		SansPapyrus683	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	281 ms	26912 KiB

jobs

#include <bits/stdc++.h>
#if __has_include("debugging.hpp")
#include "debugging.hpp"
#endif
using namespace std;

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

    int day_num;
    int max_delay;
    int job_num;
    cin >> day_num >> max_delay >> job_num;
    vector<pair<int, int>> jobs(job_num);
    for (int j = 0; j < job_num; j++) {
        cin >> jobs[j].first;
        jobs[j].first--;
        jobs[j].second = j + 1;
    }
    sort(jobs.begin(), jobs.end());

    int lo = 1;
    int hi = job_num;
    int valid = -1;
    vector<vector<int>> sched;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
    
        vector<vector<int>> buildup(day_num);
        int day_at = 0;
        for (const auto& [time, j] : jobs) {
            day_at = max(day_at, time);
            if (buildup[day_at].size() == mid) {
                day_at++;
            }
            if (day_at - time > max_delay) {
                goto bad;
            }
            buildup[day_at].push_back(j);
        }

        valid = mid;
        hi = mid - 1;
        sched = buildup;
        continue;

        bad:;
        lo = mid + 1;
    }

    cout << valid << '\n';
    for (const vector<int>& proc : sched) {
        for (int p : proc) {
            cout << p << ' ';
        }
        cout << 0 << '\n';
    }
}

• Subtask 1: 100 / 100