oj.uz

답안 #384201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384201 2021-03-31T19:05:09 Z kaplanbar Job Scheduling (CEOI12_jobs) C++14
55 / 100
 1000 ms 17076 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);
        multiset<pair<int,int>> closest;
        for(int i = 0; i < n; i++) {
            for(int x : use[i]) {
                closest.insert({i + d, x});
            }
            if(!closest.empty() && closest.begin() -> first < i) return vector<vector<int>>{};
            for(int j = 0; j < co; j++) {
                if(!closest.empty()) {
                    ans[i].push_back(closest.begin() -> second);
                    closest.erase(closest.begin());
                }
            }
        }
        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
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 903 ms 6780 KB Output is correct
2 Correct 891 ms 6828 KB Output is correct
3 Correct 900 ms 6844 KB Output is correct
4 Correct 884 ms 6852 KB Output is correct
5 Correct 897 ms 6828 KB Output is correct
6 Correct 915 ms 6852 KB Output is correct
7 Correct 914 ms 6828 KB Output is correct
8 Correct 912 ms 6780 KB Output is correct
9 Execution timed out 1092 ms 6636 KB Time limit exceeded
10 Execution timed out 1094 ms 6636 KB Time limit exceeded
11 Correct 206 ms 2540 KB Output is correct
12 Correct 620 ms 5388 KB Output is correct
13 Correct 909 ms 7932 KB Output is correct
14 Execution timed out 1088 ms 7816 KB Time limit exceeded
15 Execution timed out 1094 ms 8024 KB Time limit exceeded
16 Execution timed out 1098 ms 9604 KB Time limit exceeded
17 Execution timed out 1066 ms 11632 KB Time limit exceeded
18 Execution timed out 1040 ms 12320 KB Time limit exceeded
19 Execution timed out 1072 ms 17076 KB Time limit exceeded
20 Execution timed out 1075 ms 11740 KB Time limit exceeded