Submission #401938

#	Time	Username	Problem	Language	Result	Execution time	Memory
401938		rainliofficial	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	322 ms	23504 KiB

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