oj.uz

답안 #977997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977997 2024-05-08T15:41:47 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
30 / 100
 413 ms 17268 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
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 3420 KB Output isn't correct
2 Incorrect 35 ms 3484 KB Output isn't correct
3 Incorrect 38 ms 3420 KB Output isn't correct
4 Incorrect 39 ms 3756 KB Output isn't correct
5 Incorrect 34 ms 3416 KB Output isn't correct
6 Incorrect 36 ms 3420 KB Output isn't correct
7 Incorrect 33 ms 3412 KB Output isn't correct
8 Incorrect 36 ms 3320 KB Output isn't correct
9 Incorrect 139 ms 3516 KB Output isn't correct
10 Incorrect 141 ms 3544 KB Output isn't correct
11 Correct 31 ms 3420 KB Output is correct
12 Incorrect 71 ms 4688 KB Output isn't correct
13 Correct 107 ms 7620 KB Output is correct
14 Incorrect 148 ms 9296 KB Output isn't correct
15 Incorrect 159 ms 9812 KB Output isn't correct
16 Correct 223 ms 13828 KB Output is correct
17 Correct 259 ms 14932 KB Output is correct
18 Correct 266 ms 15304 KB Output is correct
19 Incorrect 413 ms 17268 KB Output isn't correct
20 Correct 270 ms 14796 KB Output is correct