Submission #402254

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
402254	2021-05-11T13:04:27 Z	rainliofficial	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	369 ms	23556 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	2896 KB	Output is correct
2	Correct	25 ms	2860 KB	Output is correct
3	Correct	26 ms	2892 KB	Output is correct
4	Correct	25 ms	2876 KB	Output is correct
5	Correct	25 ms	2884 KB	Output is correct
6	Correct	25 ms	2836 KB	Output is correct
7	Correct	26 ms	2868 KB	Output is correct
8	Correct	24 ms	2928 KB	Output is correct
9	Correct	42 ms	4932 KB	Output is correct
10	Correct	43 ms	4984 KB	Output is correct
11	Correct	40 ms	2752 KB	Output is correct
12	Correct	67 ms	5320 KB	Output is correct
13	Correct	101 ms	8388 KB	Output is correct
14	Correct	155 ms	11468 KB	Output is correct
15	Correct	165 ms	12500 KB	Output is correct
16	Correct	221 ms	15800 KB	Output is correct
17	Correct	288 ms	20384 KB	Output is correct
18	Correct	299 ms	20768 KB	Output is correct
19	Correct	369 ms	23556 KB	Output is correct
20	Correct	254 ms	20416 KB	Output is correct