oj.uz

답안 #384205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384205 2021-03-31T19:13:46 Z kaplanbar Job Scheduling (CEOI12_jobs) C++17
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++) {
            ans[i].clear();
            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 1039 ms 3124 KB Time limit exceeded
2 Correct 990 ms 3112 KB Output is correct
3 Execution timed out 1016 ms 3124 KB Time limit exceeded
4 Execution timed out 1016 ms 3112 KB Time limit exceeded
5 Execution timed out 1020 ms 3268 KB Time limit exceeded
6 Execution timed out 1035 ms 3124 KB Time limit exceeded
7 Execution timed out 1041 ms 3124 KB Time limit exceeded
8 Execution timed out 1090 ms 3076 KB Time limit exceeded
9 Execution timed out 1096 ms 6124 KB Time limit exceeded
10 Execution timed out 1071 ms 6124 KB Time limit exceeded
11 Correct 130 ms 2028 KB Output is correct
12 Correct 266 ms 3844 KB Output is correct
13 Correct 413 ms 6652 KB Output is correct
14 Execution timed out 1093 ms 4896 KB Time limit exceeded
15 Correct 674 ms 8804 KB Output is correct
16 Execution timed out 1093 ms 5612 KB Time limit exceeded
17 Execution timed out 1087 ms 7196 KB Time limit exceeded
18 Execution timed out 1086 ms 9452 KB Time limit exceeded
19 Execution timed out 1094 ms 13548 KB Time limit exceeded
20 Execution timed out 1086 ms 7320 KB Time limit exceeded