제출 #1150834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150834		jim_x	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	264 ms	26388 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, D, M;

pair<int, vector<vector<int>>> is_feasible(const vector<pair<int, int>>& jobs, int machine_count) {
    vector<vector<int>> schedule(N);
    int req_num = 0;

    for (int day = 1; day <= N; ++day) {
        for (int i = 0; i < machine_count; ++i) {
            if (jobs[req_num].first > day) {
                break;
            }
            if (jobs[req_num].first + D >= day) {
                schedule[day - 1].push_back(jobs[req_num].second);
                req_num++;
            } else {
                return {0, schedule};
            }
            if (req_num == M) {
                return {1, schedule};
            }
        }
    }
    return {0, schedule};
}

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

    cin >> N >> D >> M;
    vector<pair<int, int>> jobs(M);

    for (int i = 0; i < M; ++i) {
        cin >> jobs[i].first;
        jobs[i].second = i + 1;
    }

    sort(jobs.begin(), jobs.end());

    vector<vector<int>> result;
    int l = 1, r = M;

    while (l < r) {
        int machine_num = (l + r) / 2;
        auto cur_result = is_feasible(jobs, machine_num);
        if (cur_result.first) {
            r = machine_num;
            result = cur_result.second;
        } else {
            l = machine_num + 1;
        }
    }

    cout << l << "\n";
    for (int i = 0; i < N; ++i) {
        for (int idx : result[i]) {
            cout << idx << " ";
        }
        cout << "0\n";
    }

    return 0;
}

• Subtask 1: 100 / 100