Submission #1138447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138447		mrsmartypants	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	270 ms	26368 KiB

jobs

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

#define all(x) begin(x), end(x)
#define mp make_pair
using pi = pair<int, int>;
using vi = vector<int>;

int N, D, M;

pair<bool, vector<vi>> test(const vector<pi> &jobs, int machineCount) {
    vector<vi> schedule(N);
    int reqNum = 0;

    for (int day = 1; day <= N; day++) {
        for (int j = 0; j < machineCount; j++) {

            if (jobs[reqNum].first > day) break;
            if (jobs[reqNum].first + D >= day) {
                schedule[day -1].push_back(jobs[reqNum++].second);
            } else {
                return mp(false, schedule);
            }

            if (reqNum == M) return mp(true, schedule);
        }
    }
    return mp(false, schedule);
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> D >> M;
    vector<pi> jobs(M);
    for (int i = 0; i < M; i++) {
        int day;
        cin >> day;
        jobs[i] = mp(day, i+ 1);
    }
    sort(all(jobs));

    vector<vi> result;

    int l = 1;
    int r = M;
    while (l < r) {
        int machineNum = (l + r) / 2;
        pair<bool, vector<vi>> curResult = test(jobs, machineNum);


        if (curResult.first) {
            r = machineNum;
            result = curResult.second;
        } else {
            l = machineNum + 1;
        }
    }

    cout << l << "\n";
    for (int i = 0; i < N ;i++) {
        for (int &idx : result[i]) cout << idx << " ";
        cout << 0 << "\n";
    }
}

• Subtask 1: 100 / 100