oj.uz

답안 #384203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384203 2021-03-31T19:07:20 Z kaplanbar Job Scheduling (CEOI12_jobs) C++14
15 / 100
 1000 ms 13676 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 {
        multiset<pair<int,int>> closest;
        for(int i = 0; i < n; i++) {
            ans[i].clear();
            for(int x : use[i]) {
                closest.insert({i + d, x});
            }
            if(!closest.empty() && closest.begin() -> first < i) return false;
            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 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
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1060 ms 6340 KB Time limit exceeded
2 Execution timed out 1099 ms 6764 KB Time limit exceeded
3 Execution timed out 1071 ms 6380 KB Time limit exceeded
4 Execution timed out 1093 ms 6380 KB Time limit exceeded
5 Execution timed out 1093 ms 6380 KB Time limit exceeded
6 Execution timed out 1080 ms 6380 KB Time limit exceeded
7 Execution timed out 1086 ms 6380 KB Time limit exceeded
8 Execution timed out 1099 ms 6380 KB Time limit exceeded
9 Execution timed out 1091 ms 6380 KB Time limit exceeded
10 Execution timed out 1099 ms 6380 KB Time limit exceeded
11 Correct 258 ms 2156 KB Output is correct
12 Correct 631 ms 4716 KB Output is correct
13 Correct 878 ms 6636 KB Output is correct
14 Execution timed out 1057 ms 4812 KB Time limit exceeded
15 Execution timed out 1086 ms 5868 KB Time limit exceeded
16 Execution timed out 1100 ms 5484 KB Time limit exceeded
17 Execution timed out 1097 ms 7276 KB Time limit exceeded
18 Execution timed out 1095 ms 9324 KB Time limit exceeded
19 Execution timed out 1074 ms 13676 KB Time limit exceeded
20 Execution timed out 1060 ms 7276 KB Time limit exceeded