Submission #706348

#	Time	Username	Problem	Language	Result	Execution time	Memory
706348		Bodisha	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	381 ms	20108 KiB

jobs

#include <bits/stdc++.h>
#define MAX_M 1000005

using namespace std;

int n, d, m;
pair<int, int> requests[MAX_M];

bool cmp(pair<int, int> a, pair<int, int> b) {
    if(a.first == b.first) {
        return a.second < b.second;
    }
    return a.first < b.first;
}

bool check(int x) {
    int machines[x] = {0}; // end time of machines
    int max_d = 0;
    int curr_machine = 0;
    for(int i = 0, curr_machine = 0; i < m; i++, curr_machine++) {
        if(curr_machine == x) {
            curr_machine = 0;
        }
        if(machines[curr_machine] >= requests[i].first) {
            machines[curr_machine]++;
            max_d = max(max_d, machines[curr_machine] - requests[i].first);
        } else {
            machines[curr_machine] = requests[i].first;
        }
    }
    if(max_d <= d) {
        return true;
    } else {
        return false;
    }
}

int main() {
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++) {
        cin >> requests[i].first;
        requests[i].second = i + 1;
    }
    sort(requests, requests + m, cmp);
    int l = 1, r = m;
    int ans = 1;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    vector<int> result[n + 12]; 
    int machines[ans] = {0};
    for(int i = 0, curr_machine = 0; i < m; i++, curr_machine++) {
        if(curr_machine == ans) {
            curr_machine = 0;
        }
        machines[curr_machine] = max(machines[curr_machine] + 1, requests[i].first);
        result[machines[curr_machine]].push_back(requests[i].second);
    }
    cout << ans << "\n";
    for(int i = 1; i <= n; i++) {
        for(auto iter : result[i]) {
            cout << iter << " "; 
        }
        cout << "0\n";
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:19:9: warning: unused variable 'curr_machine' [-Wunused-variable]
   19 |     int curr_machine = 0;
      |         ^~~~~~~~~~~~

• Subtask 1: 100 / 100