Submission #402254

#	Time	Username	Problem	Language	Result	Execution time	Memory
402254		rainliofficial	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	369 ms	23556 KiB

jobs

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

int n, d, m;

/* Idea: Sort the time of the jobs. Then, binary search for the number of machines. To check whether x number of machines work, 
we know that it never makes sense to use machinese consecutively, because one machine will have no buffer, yet others are
sitting around waiting. From this idea, we can expand to say it ONLY makes sense to use machines in order such that they
have the MOST amount of gap between 2 usages. This means we always want to go in a cycle to use the machines (doesn't matter
the initial order), and never break that cycle. */

bool check(int mid, pair<int, int> arr[]){ // arr[] has the time a job should START
        // End is 0 based indexing, arr is 1 based.
        int end[mid]; // Tracks when a machine ENDS its job
        for (int i=0; i<mid; i++){
            end[i] = 0;
        }
        int index = 0;
        int maxD = 0;
        for (int i=0; i<m; i++){
            if (index == mid){
                index = 0;
            }
            if (end[index]+1 > arr[i].first){
                // This machine can only start later than the job starts, so there is a delaying. 
                maxD = max(maxD, end[index]+1-arr[i].first);
                end[index]++;
            }else{
                // I can start BEFORE (or equal) to the job start, so no delay
                end[index] = arr[i].first;
            }
            index++;
        }
        return maxD <= d;
}

int main(){
    cin.tie(0);ios_base::sync_with_stdio(0); // Fast IO
    cin >> n >> d >> m;
    pair<int, int> arr[m]; // Track the job start time
    for (int i=0; i<m; i++){
        int curr; cin >> curr;
        arr[i] = make_pair(curr, i+1);
    }
    sort(arr, arr+m);
    int low = 0;
    int high = m;
    while (low < high){
        int mid = (low + high)/2;
        if (check(mid, arr)){
            high = mid;
        }else{
            low = mid+1;
        }
    }
    vector<int> eachDay[n+1];
    int e[low]; // The previous END of the last job for all the machines
    for (int i=0; i<low; i++){
        e[i] = 0;
    }
    /*
    for (int i=0; i<n; i++){
        vector<int> temp;
        eachDay[i] = temp;
    }*/
    // 0 based indexing stores where my last job ended, 1 base indexing stores the time I CAN start a new job.
    for (int i=0, id = 0; i<m; i++, id++){
        if (id == low){
            id = 0;
        }
        int requestDay = arr[i].first; // 1 based indexing
        int canDo = e[id]+1; // e[] is 0 based, so +1, as we want to know when we CAN start a new job
        e[id] = max(requestDay, canDo); // Only does work when the request comes
        eachDay[e[id]].push_back(arr[i].second);
    }
    cout << low << "\n";
    for (int i=1; i<=n; i++){
        if (eachDay[i].size() != 0){
            for (int j : eachDay[i]){
                cout << j <<  " ";
            }
        }
        cout << 0 << "\n";
    }
}

• Subtask 1: 100 / 100