oj.uz

답안 #384204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384204 2021-03-31T19:09:38 Z kaplanbar Job Scheduling (CEOI12_jobs) C++14
35 / 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);
    }

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

    auto check = [&](int co) -> bool {
        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 false;
            for(int j = 0; j < co; j++) {
                if(!closest.empty()) {
                    ans[i].push_back(closest.front().second);
                    closest.pop();
                }
            }
        }
        if(!closest.empty()) return false;
        return true;
    };

    int l = 0, r = m;

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

    cout << r << "\n";

    check(r);

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

    return 0;
}

Subtask #1
35.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 997 ms 3052 KB Output is correct
2 Correct 997 ms 3180 KB Output is correct
3 Correct 1000 ms 3180 KB Output is correct
4 Execution timed out 1018 ms 3052 KB Time limit exceeded
5 Execution timed out 1012 ms 3180 KB Time limit exceeded
6 Execution timed out 1028 ms 3052 KB Time limit exceeded
7 Execution timed out 1025 ms 3052 KB Time limit exceeded
8 Execution timed out 1045 ms 3052 KB Time limit exceeded
9 Execution timed out 1053 ms 6124 KB Time limit exceeded
10 Execution timed out 1097 ms 6124 KB Time limit exceeded
11 Correct 129 ms 2156 KB Output is correct
12 Correct 262 ms 3948 KB Output is correct
13 Correct 398 ms 6600 KB Output is correct
14 Execution timed out 1092 ms 5036 KB Time limit exceeded
15 Correct 647 ms 9544 KB Output is correct
16 Execution timed out 1098 ms 5740 KB Time limit exceeded
17 Execution timed out 1096 ms 7352 KB Time limit exceeded
18 Execution timed out 1095 ms 9580 KB Time limit exceeded
19 Execution timed out 1099 ms 13548 KB Time limit exceeded
20 Execution timed out 1075 ms 7316 KB Time limit exceeded