Submission #1029511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1029511	2024-07-21T01:01:25 Z	ArthuroWich	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	290 ms	24252 KB

jobs

#include <bits/stdc++.h>
using namespace std;
bool check(vector<int> a, int mi, int n, int d) {
    int i = 1;
    while(a.size() && i <= n) {
        for (int j = 0; j < mi; j++) {
            if (a.empty()) {
                break;
            }
            if (a.back() > i) {
                break;
            }
            if (i > a.back()+d) {
                return 0;
            }
            a.pop_back();
        }
        i++;
    }
    return a.size() == 0;
}
void solve() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<int> a(m);
    vector<pair<int, int>> ans;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        ans.push_back({a[i], i});
    }
    sort(a.rbegin(), a.rend());
    sort(ans.begin(), ans.end());
    int l = 1, r = m;
    while(l < r) {
        int mi = (l+r)/2;
        if (check(a, mi, n, d)) {
            r = mi;
        } else {
            l = mi+1;
        }
    }
    cout << l << endl;
    int j = 0;
    for (int i = 0; i < n; i++) {
        int c = l;
        while(j < m && c-- && ans[j].first <= i+1) {
            cout << ans[j].second+1 << " ";
            j++;
        }
        cout << 0 << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	2772 KB	Output is correct
2	Correct	24 ms	2776 KB	Output is correct
3	Correct	24 ms	2776 KB	Output is correct
4	Correct	24 ms	2776 KB	Output is correct
5	Correct	23 ms	2772 KB	Output is correct
6	Correct	23 ms	2776 KB	Output is correct
7	Correct	24 ms	2776 KB	Output is correct
8	Correct	26 ms	2924 KB	Output is correct
9	Correct	118 ms	2960 KB	Output is correct
10	Correct	124 ms	3284 KB	Output is correct
11	Correct	25 ms	2984 KB	Output is correct
12	Correct	49 ms	5576 KB	Output is correct
13	Correct	76 ms	8724 KB	Output is correct
14	Correct	116 ms	11200 KB	Output is correct
15	Correct	116 ms	13464 KB	Output is correct
16	Correct	171 ms	18020 KB	Output is correct
17	Correct	182 ms	19388 KB	Output is correct
18	Correct	190 ms	22200 KB	Output is correct
19	Correct	290 ms	24252 KB	Output is correct
20	Correct	191 ms	19900 KB	Output is correct