Submission #1238775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238775		akanna9194	Job Scheduling (CEOI12_jobs)	C++20	45 / 100	196 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){
    for (int i = 0; i < jobs.size(); i++){
        if (((i+1) / num_of_machines) + 1 > jobs[i].first + max_delay){
            return false;
        }
    }
    return true;
}

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: 45 / 100