oj.uz

답안 #384206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384206 2021-03-31T19:15:13 Z kaplanbar Job Scheduling (CEOI12_jobs) C++14
25 / 100
 1000 ms 13548 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; j++) {
                if(!closest.empty()) {
                    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
25.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1032 ms 3060 KB Time limit exceeded
2 Correct 999 ms 3108 KB Output is correct
3 Execution timed out 1020 ms 3124 KB Time limit exceeded
4 Execution timed out 1018 ms 3112 KB Time limit exceeded
5 Execution timed out 1026 ms 3124 KB Time limit exceeded
6 Execution timed out 1041 ms 3124 KB Time limit exceeded
7 Execution timed out 1035 ms 3076 KB Time limit exceeded
8 Execution timed out 1087 ms 3112 KB Time limit exceeded
9 Execution timed out 1086 ms 6252 KB Time limit exceeded
10 Execution timed out 1088 ms 6124 KB Time limit exceeded
11 Correct 153 ms 2028 KB Output is correct
12 Correct 267 ms 3948 KB Output is correct
13 Correct 459 ms 6740 KB Output is correct
14 Execution timed out 1093 ms 4844 KB Time limit exceeded
15 Correct 672 ms 8632 KB Output is correct
16 Execution timed out 1091 ms 5740 KB Time limit exceeded
17 Execution timed out 1092 ms 7276 KB Time limit exceeded
18 Execution timed out 1087 ms 9324 KB Time limit exceeded
19 Execution timed out 1089 ms 13548 KB Time limit exceeded
20 Execution timed out 1093 ms 7404 KB Time limit exceeded