Submission #1245178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245178		caterpillow	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	246 ms	13832 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]; });

    int lo = 0, hi = m;
    vector<vector<int>> ans;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        queue<int> todo;
        bool good = true;
        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) good = false;
                tmp[i].push_back(todo.front());
                todo.pop();
            }
        }
        if (todo.size() || good == false) lo = mid;
        else {
            ans = tmp;
            hi = 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