Submission #1238779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238779		akanna9194	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	191 ms	20284 KiB

jobs

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

bool valid(int num_of_days, int max_delay, int num_of_machines, const vector<pair<int, int>>& jobs) {
    for (int i = 0; i < jobs.size(); i++) {
        int scheduled_day = (i / num_of_machines) + 1;
        if (scheduled_day > jobs[i].first + max_delay) {
            return false;
        }
    }
    return true;
}

int binary_search(int num_of_days, int max_delay, const vector<pair<int, int>>& jobs) {
    int lo = 1, hi = jobs.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (valid(num_of_days, max_delay, mid, jobs)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

void print_output(int min_machines, int num_of_days, const vector<pair<int, int>>& jobs) {
    cout << min_machines << "\n";
    vector<vector<int>> schedule(num_of_days);
    int job_index = 0;

    for (int day = 0; day < num_of_days && job_index < jobs.size(); day++) {
        for (int m = 0; m < min_machines && job_index < jobs.size(); m++) {
            schedule[day].push_back(jobs[job_index].second + 1); // +1 for 1-based index
            job_index++;
        }
    }

    for (int day = 0; day < num_of_days; day++) {
        for (int job : schedule[day]) {
            cout << job << " ";
        }
        cout << "0\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_of_days, max_delay, num_of_jobs;
    cin >> num_of_days >> max_delay >> num_of_jobs;

    vector<pair<int, int>> jobs(num_of_jobs);
    for (int i = 0; i < num_of_jobs; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i; // store original index
    }

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

    int min_machines = binary_search(num_of_days, max_delay, jobs);
    print_output(min_machines, num_of_days, jobs);

    return 0;
}

• Subtask 1: 55 / 100