Submission #977997

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977997	2024-05-08T15:41:47 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	30 / 100	413 ms	17268 KB

jobs

#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

#	Verdict	Execution time	Memory	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