Submission #706348

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706348	2023-03-06T10:02:27 Z	Bodisha	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	381 ms	20108 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	2636 KB	Output is correct
2	Correct	31 ms	2636 KB	Output is correct
3	Correct	32 ms	2612 KB	Output is correct
4	Correct	33 ms	2644 KB	Output is correct
5	Correct	33 ms	2552 KB	Output is correct
6	Correct	32 ms	2624 KB	Output is correct
7	Correct	34 ms	2636 KB	Output is correct
8	Correct	32 ms	2636 KB	Output is correct
9	Correct	40 ms	4660 KB	Output is correct
10	Correct	42 ms	4752 KB	Output is correct
11	Correct	41 ms	2368 KB	Output is correct
12	Correct	82 ms	4536 KB	Output is correct
13	Correct	125 ms	7212 KB	Output is correct
14	Correct	187 ms	9512 KB	Output is correct
15	Correct	210 ms	10572 KB	Output is correct
16	Correct	267 ms	12944 KB	Output is correct
17	Correct	313 ms	16944 KB	Output is correct
18	Correct	340 ms	17844 KB	Output is correct
19	Correct	381 ms	20108 KB	Output is correct
20	Correct	339 ms	16956 KB	Output is correct