Submission #384205

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
384205	2021-03-31T19:13:46 Z	kaplanbar	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	1000 ms	13548 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++) {
            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

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