Submission #1128363

#TimeUsernameProblemLanguageResultExecution timeMemory
1128363ewangJob Scheduling (CEOI12_jobs)C++20
0 / 100
409 ms13776 KiB
#include <bits/stdc++.h>

using namespace std;

bool ok(int machines, vector<pair<int, int>>& t, int m, int d, int n) {
    int i = 0;
    for (int day = 1; day <= n-d; day++) {
        int j = i;
        for (; j < i+machines && j < m; j++) {
            if (day < t[j].first) {
                break;
            }
        }
        i = j;
        if (i == m) {
            return true;
        }
    }
    
    return false;
}

int main() {
    int n, d, m;
    cin >> n >> d >> m;
    
    vector<pair<int, int>> t(m);
    for (int i = 0; i < m; i++) {
        cin >> t[i].first;
        t[i].second = i+1;
    }
    sort(t.begin(), t.end());
    
    int lo = 1;
    int hi = m;
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (ok(mid, t, m, d, n)) {
            hi = mid;
        } else {
            lo = mid+1;
        }
    }
    
    cout << lo << endl;
    
    int lines = 0;
    for (int i = 0; i < m; i++) {
        cout << t[i].second << " ";
        if (i%lo == lo-1) {
            cout << 0 << endl;
            lines++;
        }
    }
    
    for (int i = lines; i < n; i++) {
        cout << 0 << endl;    
    }
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...