Submission #1046676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046676	2024-08-06T20:09:14 Z	mtshasta	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	152 ms	16236 KB

jobs

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<int> jobs(m), o(m);
    vector<vector<int>> res(n);
    for (int i = 0; i < m; ++i) {
        cin >> jobs[i];
        --jobs[i];
    }
    iota(o.begin(), o.end(), 0);
    sort(o.begin(), o.end(), [&](int i, int j) { return jobs[i] < jobs[j]; });
    auto ok = [&](int mach) -> bool {
        int id = 0;
        for (int i = 0; i < n; ++i) {
            if (jobs[o[id]] > i) continue;
            int cnt = 0;
            while (id < m && jobs[o[id]] + d >= i && cnt < mach) {
                ++id;
                ++cnt;
            }
        }
        return id == m;
    };
    int l = 1, r = 1e6, ans;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (!ok(mid))
            l = mid + 1;
        else {
            ans = mid;
            r = mid - 1;
        }
    }
    cout << ans << '\n';
    int id = 0;
    for (int i = 0; i < n; ++i) {
        if (jobs[o[id]] <= i) {
            int cnt = 0;
            while (id < m && jobs[o[id]] + d >= i && cnt < ans) {
                cout << o[id] + 1 << ' ';
                ++id;
                ++cnt;
            }
        }
        cout << 0 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:44:51: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |             while (id < m && jobs[o[id]] + d >= i && cnt < ans) {
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	1884 KB	Output is correct
2	Correct	11 ms	1884 KB	Output is correct
3	Correct	14 ms	1880 KB	Output is correct
4	Correct	11 ms	1884 KB	Output is correct
5	Correct	11 ms	1884 KB	Output is correct
6	Correct	14 ms	1884 KB	Output is correct
7	Correct	11 ms	1884 KB	Output is correct
8	Correct	11 ms	1884 KB	Output is correct
9	Correct	17 ms	4292 KB	Output is correct
10	Correct	18 ms	4368 KB	Output is correct
11	Correct	17 ms	1628 KB	Output is correct
12	Correct	32 ms	3328 KB	Output is correct
13	Correct	49 ms	4692 KB	Output is correct
14	Correct	88 ms	6384 KB	Output is correct
15	Correct	80 ms	7764 KB	Output is correct
16	Correct	106 ms	9308 KB	Output is correct
17	Correct	120 ms	10832 KB	Output is correct
18	Correct	145 ms	12328 KB	Output is correct
19	Correct	152 ms	16236 KB	Output is correct
20	Correct	126 ms	10836 KB	Output is correct