oj.uz

답안 #977999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977999 2024-05-08T15:46:52 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 400 ms 13648 KB 
#include<iostream>
#include<algorithm>
using namespace std;

int n, d, m; // available days, max delay, job count
pair<int, int> arrive[1000001]; // when the jobs come in

bool isok(int machines) {
    int current = 0;
    for (int i = 1; i <= n; i++) {
        int machines_left = machines;
        while (machines_left > 0 && current < m && arrive[current].first <= i) {
            if (i - arrive[current].first > d) {
                return false;
            }

            machines_left--;
            current++;
        }
    }

    return current == m; // can complete all jobs
}

int main() {
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        cin >> arrive[i].first;
        arrive[i].second = i + 1;
    }

    sort(arrive, arrive + m);

    int left = 1, right = m;
    int ans = 1;

    while (left <= right) {
        int mid = (left + right) / 2; // bsearch for how many machines needed
        if (isok(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << endl;

    int current = 0;
    for (int i = 1; i <= n; i++) {
        int machines_left = ans;
        while (machines_left > 0 && current < m && arrive[current].first <= i) {
            cout << arrive[current].second << " ";

            machines_left--;
            current++;
        }

        cout << 0 << endl;
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 3152 KB Output is correct
2 Correct 41 ms 3164 KB Output is correct
3 Correct 37 ms 3420 KB Output is correct
4 Correct 33 ms 3156 KB Output is correct
5 Correct 34 ms 3160 KB Output is correct
6 Correct 34 ms 3264 KB Output is correct
7 Correct 33 ms 3164 KB Output is correct
8 Correct 33 ms 3176 KB Output is correct
9 Correct 139 ms 3232 KB Output is correct
10 Correct 135 ms 3428 KB Output is correct
11 Correct 32 ms 3156 KB Output is correct
12 Correct 63 ms 3928 KB Output is correct
13 Correct 94 ms 6480 KB Output is correct
14 Correct 147 ms 7264 KB Output is correct
15 Correct 173 ms 8016 KB Output is correct
16 Correct 219 ms 10836 KB Output is correct
17 Correct 257 ms 11372 KB Output is correct
18 Correct 262 ms 12116 KB Output is correct
19 Correct 400 ms 13648 KB Output is correct
20 Correct 257 ms 11732 KB Output is correct