oj.uz

Submission #692571

# Submission time Handle Problem Language Result Execution time Memory
692571 2023-02-02T00:16:06 Z Snowmanonahoe Job Scheduling (CEOI12_jobs) C++17
100 / 100
 380 ms 20208 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> jobs;
int N, M, D;
optional<vector<vector<int>>> check(int num) {
    vector<vector<int>> schedule(N+1);
    queue<pair<int, int>> jobQueue;
    for (int i = 1, j = 1; i <= N; i++) {
        while (j <= M && jobs[j].first == i) {
            jobQueue.push(jobs[j]);
            j++;
        }
        for (int k = 0; k < num && !jobQueue.empty(); k++) {
            if (jobQueue.front().first + D < i)
                return nullopt;
            schedule[i].push_back(jobQueue.front().second);
            jobQueue.pop();
        }
    }
    if (jobQueue.empty())
        return schedule;
    return nullopt;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> D >> M;
    jobs.resize(M+1);
    for (int i = 1; i <= M; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i;
    }
    sort(jobs.begin()+1, jobs.end());
    int l = 1, r = M;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << '\n';
    auto ans = *check(l);
    for (int i = 1; i <= N; i++) {
        for (auto j : ans[i])
            cout << j << ' ';
        cout << "0\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3372 KB Output is correct
2 Correct 31 ms 3472 KB Output is correct
3 Correct 32 ms 3440 KB Output is correct
4 Correct 31 ms 3352 KB Output is correct
5 Correct 31 ms 3368 KB Output is correct
6 Correct 31 ms 3444 KB Output is correct
7 Correct 37 ms 3424 KB Output is correct
8 Correct 31 ms 3516 KB Output is correct
9 Correct 45 ms 4900 KB Output is correct
10 Correct 50 ms 5064 KB Output is correct
11 Correct 38 ms 2156 KB Output is correct
12 Correct 80 ms 4320 KB Output is correct
13 Correct 114 ms 6620 KB Output is correct
14 Correct 175 ms 9164 KB Output is correct
15 Correct 194 ms 9652 KB Output is correct
16 Correct 244 ms 12964 KB Output is correct
17 Correct 323 ms 15956 KB Output is correct
18 Correct 327 ms 16564 KB Output is correct
19 Correct 380 ms 20208 KB Output is correct
20 Correct 303 ms 16080 KB Output is correct