Submission #1046666

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046666	2024-08-06T20:01:46 Z	mtshasta	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	146 ms	19536 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) {
            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) {
        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:42:47: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |         while (id < m && jobs[o[id]] + d >= i && cnt < ans) {
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	2396 KB	Output isn't correct
2	Incorrect	11 ms	2300 KB	Output isn't correct
3	Incorrect	11 ms	2336 KB	Output isn't correct
4	Incorrect	10 ms	2140 KB	Output isn't correct
5	Incorrect	11 ms	2396 KB	Output isn't correct
6	Incorrect	11 ms	2252 KB	Output isn't correct
7	Incorrect	11 ms	2392 KB	Output isn't correct
8	Incorrect	12 ms	2512 KB	Output isn't correct
9	Correct	18 ms	4440 KB	Output is correct
10	Correct	18 ms	4440 KB	Output is correct
11	Correct	15 ms	2140 KB	Output is correct
12	Correct	31 ms	3956 KB	Output is correct
13	Correct	48 ms	5968 KB	Output is correct
14	Correct	85 ms	8292 KB	Output is correct
15	Incorrect	81 ms	9552 KB	Output isn't correct
16	Correct	104 ms	12372 KB	Output is correct
17	Correct	133 ms	14208 KB	Output is correct
18	Correct	129 ms	15368 KB	Output is correct
19	Correct	146 ms	19536 KB	Output is correct
20	Correct	126 ms	14160 KB	Output is correct