Submission #1312262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312262		anass.b	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	191 ms	20924 KiB

jobs

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

using ull = unsigned long long;

bool can_schedule(const vector<pair<ull,int>>& jobs, ull d, ull m) {
    ull day = 0, used = 0;

    for (auto &[job, _] : jobs) {
        while (day < job) {
            day++;
            used = 0;
        }

        if (day <= job + d) {
            used++;
            if (used == m) {
                day++;
                used = 0;
            }
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ull n, d, m;
    cin >> n >> d >> m;

    vector<pair<ull,int>> jobs(m);
    for (int i = 0; i < (int)m; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i + 1; // 1-based index
    }

    sort(jobs.begin(), jobs.end());

    // Binary search minimal machines
    ull left = 1, right = m;
    if (can_schedule(jobs, d, 1)) {
        right = 1;
    } else {
        while (left < right - 1) {
            ull mid = left + (right - left) / 2;
            if (can_schedule(jobs, d, mid))
                right = mid;
            else
                left = mid;
        }
    }

    cout << right << "\n";

    // ---- PRINT SCHEDULE (NO STORAGE) ----
    ull day = 1, used = 0;
    int i = 0; // pointer over jobs

    for (ull cur_day = 1; cur_day <= n; cur_day++) {
        bool printed = false;

        while (i < (int)m) {
            ull job_day = jobs[i].first;

            if (day < job_day) {
                day++;
                used = 0;
                break;
            }

            if (day != cur_day) break;

            if (day <= job_day + d) {
                cout << jobs[i].second << " ";
                printed = true;
                used++;
                i++;

                if (used == right) {
                    day++;
                    used = 0;
                    break;
                }
            } else {
                // impossible state should not happen
                break;
            }
        }

        cout << 0 << "\n";
    }

    return 0;
}

• Subtask 1: 100 / 100