Submission #1245188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245188		caterpillow	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	96 ms	9936 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, d, m;
    cin >> n >> d >> m;
    vector<int> reqs(m), ord(m);
    for (int &x : reqs) cin >> x, x--;
    for (int i = 0; i < m; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), [&] (int i, int j) { return reqs[i] < reqs[j]; });

    auto check = [&] (int mid) -> vector<vector<int>> {
        queue<int> todo;
        int j = 0;
        vector<vector<int>> tmp(n);
        for (int i = 0; i < n; i++) {
            while (j < m && reqs[ord[j]] == i) todo.push(ord[j++]);
            for (int k = 0; k < mid && todo.size(); k++) {
                if (i - todo.front() > d) return {};
                tmp[i].push_back(todo.front());
                todo.pop();
            }
        }
        if (todo.size()) return {};
        return tmp;
    };

    int lo = 0, hi = m + 1;
    vector<vector<int>> ans;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        auto res = check(mid);
        if (res.size()) hi = mid, ans = res;
        else lo = mid;
    }
    cout << hi << '\n';
    // for (int i = 0; i < n; i++) {
        // for (int x : ans[i]) cout << x + 1 << ' ';
        // cout << "0\n";
    // }
}

• Subtask 1: 0 / 100