Submission #466318

#	Time	Username	Problem	Language	Result	Execution time	Memory
466318		nehasane	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	477 ms	13744 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, d, m;
    cin >> n >> d >> m;
    vector <pair<int, int>> jobs(m);
    for (int i = 0; i < m; i++){
        cin >> jobs[i].first;
        jobs[i].second = i;
    }
    sort(begin(jobs), end(jobs));
    int l = 1, r = m;
    while (l <= r){
        int machines = (l+r) / 2;
        int i = 0;
        for (int day = 1; day <= n; day++){
            for (int j = 0; j < machines; j++){
                if (i >= m)
                    break;
                if (day - jobs[i].first <= d && day >= jobs[i].first)
                    i++;
                else
                    break;
            }
            if (i >= m)
                break;
        }
        if (i >= m)
            r = machines - 1;
        else
            l = machines + 1;
    }
    cout << l << '\n';
    int i = 0;
    for (int day = 1; day <= n; day++){
        for (int j = 0; j < l; j++){
            if (i >= m)
                break;
            if (day - jobs[i].first <= d && day >= jobs[i].first){
                cout << jobs[i].second + 1 << ' ';
                i++;
            }
        }
        cout << 0 << '\n';
    }


}

• Subtask 1: 100 / 100