oj.uz

Submission #716084

# Submission time Handle Problem Language Result Execution time Memory
716084 2023-03-28T23:11:45 Z SnowRaven52 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 639 ms 30252 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, d, m;
    cin >> n >> d >> m;
	
    vector<pair<int, int>> t(m);
    for (int i = 0; i < m; i++) {
        cin >> t[i].first;
        t[i].second = i + 1;
    }

    sort(t.begin(), t.end());
    vector<vector<int>> res;
    int l = 0, r = m;

    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        vector<vector<int>> cur(n + 1);
        queue<int> q;
        for (int i = 0; i < mid; i++) {
            q.push(0);
        }

        bool works = true;
        for (int i = 0; i < m; i++) {
            if (q.front() - d <= t[i].first) {
                int jt = max(q.front(), t[i].first);
                q.push(jt + 1);
                cur[jt].push_back(t[i].second);
                q.pop();
            } else {
                works = false;
                break;
            }
        }

        if (works) {
            r = mid;
            res = cur;
        } else {
            l = mid;
        }
    }

    cout << r << endl;
    for (int i = 1; i <= n; i++) {
        for (int x : res[i]) {
            cout << x << " ";
        }
        cout << 0 << endl;
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3248 KB Output is correct
2 Correct 62 ms 3244 KB Output is correct
3 Correct 62 ms 3276 KB Output is correct
4 Correct 62 ms 3280 KB Output is correct
5 Correct 63 ms 3240 KB Output is correct
6 Correct 58 ms 3296 KB Output is correct
7 Correct 62 ms 3240 KB Output is correct
8 Correct 59 ms 3292 KB Output is correct
9 Correct 172 ms 8080 KB Output is correct
10 Correct 177 ms 8076 KB Output is correct
11 Correct 54 ms 3172 KB Output is correct
12 Correct 108 ms 6052 KB Output is correct
13 Correct 162 ms 9540 KB Output is correct
14 Correct 244 ms 13296 KB Output is correct
15 Correct 249 ms 15068 KB Output is correct
16 Correct 344 ms 19164 KB Output is correct
17 Correct 424 ms 23048 KB Output is correct
18 Correct 477 ms 24024 KB Output is correct
19 Correct 639 ms 30252 KB Output is correct
20 Correct 431 ms 22896 KB Output is correct