제출 #1238777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238777		akanna9194	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	218 ms	20200 KiB

jobs

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

// Check if it's possible to process all jobs using 'num_of_machines' machines
bool valid(int& num_of_days, int& max_delay, int& num_of_machines, vector<pair<int, int>>& jobs) {
    for (int i = 0; i < jobs.size(); i++) {
        int curr_day = (int)ceil((i + 1.0) / num_of_machines);
        if (curr_day > jobs[i].first + max_delay) {
            return false;
        }
    }
    return true;
}

// Binary search to find the minimum number of machines required
int binary_search(int& num_of_days, int& max_delay, vector<pair<int, int>>& jobs) {
    int lo = 1, hi = jobs.size();  // start from 1 (0 is invalid)
    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 hi;
}

// Output the machine count and feasible schedule
void print_output(int min_machines, int& num_of_days, vector<pair<int, int>>& jobs) {
    cout << min_machines << "\n";

    vector<vector<int>> day_to_job_index(num_of_days);  // day -> job IDs
    for (int i = 0; i < jobs.size(); i++) {
        int curr_day = (int)ceil((i + 1.0) / min_machines);
        if (curr_day <= num_of_days) {
            day_to_job_index[curr_day - 1].push_back(jobs[i].second + 1);  // convert to 1-based job index
        }
    }

    for (int i = 0; i < num_of_days; i++) {
        for (int job_id : day_to_job_index[i]) {
            cout << job_id << " ";
        }
        cout << "0\n";  // end of line marker
    }
}

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;  // submission day
        jobs[i].second = i;    // original index (job id)
    }

    sort(jobs.begin(), jobs.end());  // sort by submission day
    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