oj.uz

답안 #384207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384207 2021-03-31T19:16:35 Z kaplanbar Job Scheduling (CEOI12_jobs) C++14
100 / 100
 406 ms 20004 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d, m;
    cin >> n >> d >> m;

    vector<vector<int>> use(n);

    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        use[x - 1].push_back(i);
    }

    auto check = [&](int co) -> vector<vector<int>> {
        vector<vector<int>> ans(n);
        queue<pair<int,int>> closest;
        for(int i = 0; i < n; i++) {
            for(int x : use[i]) {
                closest.push({i + d, x});
            }
            if(!closest.empty() && closest.front().first < i) return vector<vector<int>>{};
            for(int j = 0; j < co && !closest.empty(); j++) {
                ans[i].push_back(closest.front().second);
                closest.pop();
            }
        }
        if(!closest.empty()) return vector<vector<int>>{};
        return ans;
    };

    int l = 0, r = m;

    while(l + 1 < r) {
        int mid = (l + r) / 2;
        if(!check(mid).empty()) r = mid;
        else l = mid; 
    }

    cout << r << "\n";

    auto ans = check(r);

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

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 3112 KB Output is correct
2 Correct 41 ms 3112 KB Output is correct
3 Correct 39 ms 3112 KB Output is correct
4 Correct 39 ms 3112 KB Output is correct
5 Correct 40 ms 3112 KB Output is correct
6 Correct 39 ms 3112 KB Output is correct
7 Correct 39 ms 3112 KB Output is correct
8 Correct 39 ms 3112 KB Output is correct
9 Correct 54 ms 7104 KB Output is correct
10 Correct 53 ms 7228 KB Output is correct
11 Correct 37 ms 2028 KB Output is correct
12 Correct 82 ms 3892 KB Output is correct
13 Correct 125 ms 6652 KB Output is correct
14 Correct 192 ms 9040 KB Output is correct
15 Correct 194 ms 8632 KB Output is correct
16 Correct 260 ms 12160 KB Output is correct
17 Correct 351 ms 16068 KB Output is correct
18 Correct 340 ms 14980 KB Output is correct
19 Correct 406 ms 20004 KB Output is correct
20 Correct 330 ms 15992 KB Output is correct