Submission #1312017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312017		quacksire	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	475 ms	20480 KiB

jobs

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

struct Job {
    int day, idx;
};

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

    int N, D, M;
    cin >> N >> D >> M;

    vector<Job> array(M);
    for (int i = 0; i < M; ++i) {
        cin >> array[i].day;
        array[i].idx = i + 1;
    }

    int lo = 1, hi = M;
    int best = M;

    auto work = [&](int k) {
        vector<int> temp(N+1, 0);
        sort(array.begin(), array.end(), [](Job a, Job b){ return a.day < b.day; });
        for (auto& job : array) {
            bool done = false;
            for (int d = job.day; d <= min(N, job.day + D); ++d) {
                if (temp[d] < k) {
                    temp[d]++;
                    done = true;
                    break;
                }
            }
            if (!done) return false;
        }
        return true;
    };

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

    vector<vector<int>> ans(N+1);
    vector<int> cnt(N+1, 0);
    sort(array.begin(), array.end(), [](Job a, Job b){ return a.day < b.day; });
    for (auto& job : array) {
        for (int d = job.day; d <= min(N, job.day + D); ++d) {
            if (cnt[d] < best) {
                ans[d].push_back(job.idx);
                cnt[d]++;
                break;
            }
        }
    }

    cout << best << '\n';
    for (int d = 1; d <= N; ++d) {
        for (int id : ans[d]) cout << id << ' ';
        cout << 0 << '\n';
    }

    return 0;
}

• Subtask 1: 100 / 100