Submission #692571

#	Time	Username	Problem	Language	Result	Execution time	Memory
692571		Snowmanonahoe	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	380 ms	20208 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> jobs;
int N, M, D;
optional<vector<vector<int>>> check(int num) {
    vector<vector<int>> schedule(N+1);
    queue<pair<int, int>> jobQueue;
    for (int i = 1, j = 1; i <= N; i++) {
        while (j <= M && jobs[j].first == i) {
            jobQueue.push(jobs[j]);
            j++;
        }
        for (int k = 0; k < num && !jobQueue.empty(); k++) {
            if (jobQueue.front().first + D < i)
                return nullopt;
            schedule[i].push_back(jobQueue.front().second);
            jobQueue.pop();
        }
    }
    if (jobQueue.empty())
        return schedule;
    return nullopt;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> D >> M;
    jobs.resize(M+1);
    for (int i = 1; i <= M; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i;
    }
    sort(jobs.begin()+1, jobs.end());
    int l = 1, r = M;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << '\n';
    auto ans = *check(l);
    for (int i = 1; i <= N; i++) {
        for (auto j : ans[i])
            cout << j << ' ';
        cout << "0\n";
    }
}

• Subtask 1: 100 / 100