Submission #384201

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
384201	2021-03-31T19:05:09 Z	kaplanbar	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	1000 ms	17076 KB

jobs

#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

#	Verdict	Execution time	Memory	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