Submission #1238783

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

jobs

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

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

int binary_search(int& num_of_days, int& max_delay, vector<pair<int, int>>& jobs){
    int lo = 0, 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 hi;
}

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);
    for (int i = 0; i < jobs.size(); i++){
        int curr_day = ceil((i+1.0) / min_machines);
        day_to_job_index[curr_day-1].push_back(jobs[i].second+1);
    }
    for (int i = 0; i < num_of_days; i++){
        for (int j = 0; j < day_to_job_index[i].size(); j++){
            cout << day_to_job_index[i][j] << " ";
        }
        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;
    }
    sort(jobs.begin(), jobs.end());
    print_output(binary_search(num_of_days, max_delay, jobs), num_of_days, jobs);
}

• Subtask 1: 100 / 100