Submission #401938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
401938	2021-05-11T03:04:37 Z	rainliofficial	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	322 ms	23504 KB

jobs

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

int n, d, m;

bool check(int mid, pair<int, int> arr[]){
        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){
                maxD = max(maxD, end[index]+1-arr[i].first);
                end[index]++;
            }else{
                end[index] = arr[i].first; // No delay
            }
            index++;
        }
        return maxD <= d;
}

int main(){
    cin.tie(0);ios_base::sync_with_stdio(0);
    cin >> n >> d >> m;
    pair<int, int> arr[m];
    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];
    for (int i=0; i<low; i++){
        e[i] = 0;
    }
    for (int i=0; i<n; i++){
        vector<int> temp;
        eachDay[i] = temp;
    }
    for (int i=0, id = 0; i<m; i++, id++){
        if (id == low){
            id = 0;
        }
        int requestDay = arr[i].first;
        int canDo = e[id]+1;
        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	2536 KB	Output is correct
2	Correct	25 ms	2632 KB	Output is correct
3	Correct	26 ms	2616 KB	Output is correct
4	Correct	25 ms	2644 KB	Output is correct
5	Correct	26 ms	2636 KB	Output is correct
6	Correct	25 ms	2608 KB	Output is correct
7	Correct	30 ms	2652 KB	Output is correct
8	Correct	26 ms	2632 KB	Output is correct
9	Correct	42 ms	4804 KB	Output is correct
10	Correct	53 ms	4792 KB	Output is correct
11	Correct	33 ms	2492 KB	Output is correct
12	Correct	68 ms	4700 KB	Output is correct
13	Correct	102 ms	7380 KB	Output is correct
14	Correct	142 ms	9668 KB	Output is correct
15	Correct	172 ms	10860 KB	Output is correct
16	Correct	213 ms	13080 KB	Output is correct
17	Correct	257 ms	20264 KB	Output is correct
18	Correct	281 ms	20676 KB	Output is correct
19	Correct	322 ms	23504 KB	Output is correct
20	Correct	251 ms	20364 KB	Output is correct