Submission #1063588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063588	2024-08-17T21:00:16 Z	DeathIsAwe	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	231 ms	20624 KB

jobs

#include <bits/stdc++.h>
using namespace std;


bool schedule(vector<int> requests, int n, int d, int m, int a) {
    bool ans = true;
    int counter;
    for (int i=0;i<n;i++) {
        counter = 0;
        while (counter < a && requests.size() > 0 && requests[requests.size() - 1] < i + 2) {
            counter++;
            if (requests[requests.size() - 1] < i - d + 1) {
                ans = false;
                break;
            }
            requests.pop_back();
        }
        if (!ans) {
            break;
        }
    }
    if (requests.size() > 0) {
        ans = false;
    }
    return ans;
}


int main() {
    int n, d, m; cin >> n >> d >> m;
    vector<int> requests(m);
    vector<vector<int>> requestmapper(n + 1);
    for (int i=0;i<m;i++) {
        cin >> requests[i];
        requestmapper[requests[i]].push_back(i + 1);
    }
    sort(requests.begin(), requests.end(), greater<int>());

    int top = m, bottom = 0, middle;
    while (top > bottom + 1) {
        middle = (top + bottom) / 2;
        if (schedule(requests, n, d, m, middle)) {
            top = middle;
        } else {
            bottom = middle;
        }
    }



    int counter, temp;
    cout << top << '\n';
    for (int i=0;i<n;i++) {
        counter = 0;
        while (counter < top && requests.size() > 0 && requests[requests.size() - 1] < i + 2) {
            temp = requests[requests.size() - 1];
            counter++;
            cout << requestmapper[temp][requestmapper[temp].size() - 1] << ' ';
            requestmapper[temp].pop_back();
            requests.pop_back();
        }
        cout << 0 << '\n';
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2376 KB	Output is correct
2	Correct	19 ms	2376 KB	Output is correct
3	Correct	19 ms	2380 KB	Output is correct
4	Correct	19 ms	2424 KB	Output is correct
5	Correct	19 ms	2380 KB	Output is correct
6	Correct	19 ms	2376 KB	Output is correct
7	Correct	19 ms	2376 KB	Output is correct
8	Correct	19 ms	2380 KB	Output is correct
9	Correct	32 ms	4808 KB	Output is correct
10	Correct	28 ms	4812 KB	Output is correct
11	Correct	24 ms	2260 KB	Output is correct
12	Correct	49 ms	4324 KB	Output is correct
13	Correct	72 ms	7100 KB	Output is correct
14	Correct	122 ms	8944 KB	Output is correct
15	Correct	123 ms	10668 KB	Output is correct
16	Correct	168 ms	13396 KB	Output is correct
17	Correct	195 ms	16076 KB	Output is correct
18	Correct	204 ms	16920 KB	Output is correct
19	Correct	231 ms	20624 KB	Output is correct
20	Correct	197 ms	16028 KB	Output is correct