oj.uz

답안 #1046676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046676 2024-08-06T20:09:14 Z mtshasta Job Scheduling (CEOI12_jobs) C++17
100 / 100
 152 ms 16236 KB 
#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

# 결과 실행 시간 메모리 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