Submission #384204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
384204	2021-03-31T19:09:38 Z	kaplanbar	Job Scheduling (CEOI12_jobs)	C++14	35 / 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);
    }

    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

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