Submission #384207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
384207	2021-03-31T19:16:35 Z	kaplanbar	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	406 ms	20004 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);
        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 && !closest.empty(); j++) {
                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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	3112 KB	Output is correct
2	Correct	41 ms	3112 KB	Output is correct
3	Correct	39 ms	3112 KB	Output is correct
4	Correct	39 ms	3112 KB	Output is correct
5	Correct	40 ms	3112 KB	Output is correct
6	Correct	39 ms	3112 KB	Output is correct
7	Correct	39 ms	3112 KB	Output is correct
8	Correct	39 ms	3112 KB	Output is correct
9	Correct	54 ms	7104 KB	Output is correct
10	Correct	53 ms	7228 KB	Output is correct
11	Correct	37 ms	2028 KB	Output is correct
12	Correct	82 ms	3892 KB	Output is correct
13	Correct	125 ms	6652 KB	Output is correct
14	Correct	192 ms	9040 KB	Output is correct
15	Correct	194 ms	8632 KB	Output is correct
16	Correct	260 ms	12160 KB	Output is correct
17	Correct	351 ms	16068 KB	Output is correct
18	Correct	340 ms	14980 KB	Output is correct
19	Correct	406 ms	20004 KB	Output is correct
20	Correct	330 ms	15992 KB	Output is correct