Submission #1063588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063588		DeathIsAwe	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	231 ms	20624 KiB

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 / 100