Submission #1222889

#TimeUsernameProblemLanguageResultExecution timeMemory
1222889toast12Job Scheduling (CEOI12_jobs)C++20
100 / 100
317 ms26864 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    vector<vector<int>> ans;
    int lo = 1, hi = m;
    while (lo < hi) {
        int mid = (lo+hi)/2;
        int day = 1;
        vector<vector<int>> v(n+1);
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (cnt == mid) {
                day++;
                cnt = 0;
            }
            if (a[i].first > day) {
                day = a[i].first;
                cnt = 0;
            }
            else if (day > a[i].first+d) {
                v.clear();
                break;
            }
            v[day].push_back(a[i].second+1);
            cnt++;
        }
        if (!v.empty()) {
            hi = mid;
            ans = v;
        }
        else lo = mid+1;
    }
    cout << hi << '\n';
    for (int i = 1; i <= n; i++) {
        for (auto x : ans[i]) cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...