Submission #742927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742927	2023-05-17T06:12:03 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	206 ms	17164 KB

jobs

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_M = 1e6 + 10;
 
int N, D, M;
int S[MAX_M], id[MAX_M];
 
bool solve(int mid) {
    int i = 1;
    for(int days = 1; days <= N and i <= M; days++) {
        if(days > S[id[i]] + D) {
            break;
        }
 
        int cnt = mid;
        while(i <= M and S[id[i]] <= days and cnt--) {
            i++;
        }
    }
    return i == M + 1;
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> N >> D >> M;
    for(int i = 1; i <= M; i++) {
        cin >> S[i];
        id[i] = i;
    }
 
    sort(id + 1, id + M + 1, [&](const int &a, const int &b) {
        return S[a] < S[b];
    });
 
    int l = 1, r = M, ans = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
 
        if(solve(mid) == true) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
 
    cout << ans << '\n';
    for(int i = 1, j = 1; i <= N; i++) {
        for(int k = 0; j <= M and k < ans; j++, k++) {
            cout << id[j] << ' ';
        }
        cout << "0\n";
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1976 KB	Output is correct
2	Correct	17 ms	1924 KB	Output is correct
3	Correct	20 ms	1988 KB	Output is correct
4	Correct	16 ms	2004 KB	Output is correct
5	Correct	17 ms	2004 KB	Output is correct
6	Correct	18 ms	1964 KB	Output is correct
7	Correct	18 ms	1996 KB	Output is correct
8	Correct	16 ms	2016 KB	Output is correct
9	Correct	21 ms	2048 KB	Output is correct
10	Correct	22 ms	2136 KB	Output is correct
11	Correct	25 ms	2056 KB	Output is correct
12	Correct	47 ms	3900 KB	Output is correct
13	Correct	73 ms	5716 KB	Output is correct
14	Correct	102 ms	8064 KB	Output is correct
15	Correct	118 ms	9444 KB	Output is correct
16	Correct	145 ms	11900 KB	Output is correct
17	Correct	173 ms	13856 KB	Output is correct
18	Correct	195 ms	15100 KB	Output is correct
19	Correct	206 ms	17164 KB	Output is correct
20	Correct	186 ms	13836 KB	Output is correct