oj.uz

답안 #1029511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029511 2024-07-21T01:01:25 Z ArthuroWich Job Scheduling (CEOI12_jobs) C++17
100 / 100
 290 ms 24252 KB 
#include <bits/stdc++.h>
using namespace std;
bool check(vector<int> a, int mi, int n, int d) {
    int i = 1;
    while(a.size() && i <= n) {
        for (int j = 0; j < mi; j++) {
            if (a.empty()) {
                break;
            }
            if (a.back() > i) {
                break;
            }
            if (i > a.back()+d) {
                return 0;
            }
            a.pop_back();
        }
        i++;
    }
    return a.size() == 0;
}
void solve() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<int> a(m);
    vector<pair<int, int>> ans;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        ans.push_back({a[i], i});
    }
    sort(a.rbegin(), a.rend());
    sort(ans.begin(), ans.end());
    int l = 1, r = m;
    while(l < r) {
        int mi = (l+r)/2;
        if (check(a, mi, n, d)) {
            r = mi;
        } else {
            l = mi+1;
        }
    }
    cout << l << endl;
    int j = 0;
    for (int i = 0; i < n; i++) {
        int c = l;
        while(j < m && c-- && ans[j].first <= i+1) {
            cout << ans[j].second+1 << " ";
            j++;
        }
        cout << 0 << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2772 KB Output is correct
2 Correct 24 ms 2776 KB Output is correct
3 Correct 24 ms 2776 KB Output is correct
4 Correct 24 ms 2776 KB Output is correct
5 Correct 23 ms 2772 KB Output is correct
6 Correct 23 ms 2776 KB Output is correct
7 Correct 24 ms 2776 KB Output is correct
8 Correct 26 ms 2924 KB Output is correct
9 Correct 118 ms 2960 KB Output is correct
10 Correct 124 ms 3284 KB Output is correct
11 Correct 25 ms 2984 KB Output is correct
12 Correct 49 ms 5576 KB Output is correct
13 Correct 76 ms 8724 KB Output is correct
14 Correct 116 ms 11200 KB Output is correct
15 Correct 116 ms 13464 KB Output is correct
16 Correct 171 ms 18020 KB Output is correct
17 Correct 182 ms 19388 KB Output is correct
18 Correct 190 ms 22200 KB Output is correct
19 Correct 290 ms 24252 KB Output is correct
20 Correct 191 ms 19900 KB Output is correct