Submission #977999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977999	2024-05-08T15:46:52 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	400 ms	13648 KB

jobs

#include<iostream>
#include<algorithm>
using namespace std;

int n, d, m; // available days, max delay, job count
pair<int, int> arrive[1000001]; // when the jobs come in

bool isok(int machines) {
    int current = 0;
    for (int i = 1; i <= n; i++) {
        int machines_left = machines;
        while (machines_left > 0 && current < m && arrive[current].first <= i) {
            if (i - arrive[current].first > d) {
                return false;
            }

            machines_left--;
            current++;
        }
    }

    return current == m; // can complete all jobs
}

int main() {
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        cin >> arrive[i].first;
        arrive[i].second = i + 1;
    }

    sort(arrive, arrive + m);

    int left = 1, right = m;
    int ans = 1;

    while (left <= right) {
        int mid = (left + right) / 2; // bsearch for how many machines needed
        if (isok(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << endl;

    int current = 0;
    for (int i = 1; i <= n; i++) {
        int machines_left = ans;
        while (machines_left > 0 && current < m && arrive[current].first <= i) {
            cout << arrive[current].second << " ";

            machines_left--;
            current++;
        }

        cout << 0 << endl;
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	3152 KB	Output is correct
2	Correct	41 ms	3164 KB	Output is correct
3	Correct	37 ms	3420 KB	Output is correct
4	Correct	33 ms	3156 KB	Output is correct
5	Correct	34 ms	3160 KB	Output is correct
6	Correct	34 ms	3264 KB	Output is correct
7	Correct	33 ms	3164 KB	Output is correct
8	Correct	33 ms	3176 KB	Output is correct
9	Correct	139 ms	3232 KB	Output is correct
10	Correct	135 ms	3428 KB	Output is correct
11	Correct	32 ms	3156 KB	Output is correct
12	Correct	63 ms	3928 KB	Output is correct
13	Correct	94 ms	6480 KB	Output is correct
14	Correct	147 ms	7264 KB	Output is correct
15	Correct	173 ms	8016 KB	Output is correct
16	Correct	219 ms	10836 KB	Output is correct
17	Correct	257 ms	11372 KB	Output is correct
18	Correct	262 ms	12116 KB	Output is correct
19	Correct	400 ms	13648 KB	Output is correct
20	Correct	257 ms	11732 KB	Output is correct