제출 #1238781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238781		akanna9194	Job Scheduling (CEOI12_jobs)	C++20	100 / 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) {
    int job_idx = 0;
    int m = jobs.size();
    for (int day = 1; day <= num_of_days; day++) {
        int machines_used = 0;
        while (machines_used < num_of_machines && job_idx < m && jobs[job_idx].first <= day) {
            if (jobs[job_idx].first + max_delay < day) return false;
            machines_used++;
            job_idx++;
        }
        if (job_idx == m) return true;
    }
    return job_idx == m;
}


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);
}

/*

8 2 12
1 2 4 2 1 3 5 6 2 3 6 4 

3 3 4 4 4 5 5 6 6 7 8 8
*/

• Subtask 1: 100 / 100