Submission #556847

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
556847	2022-05-04T06:23:20 Z	Jomnoi	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	212 ms	13840 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	1620 KB	Output is correct
2	Correct	17 ms	1748 KB	Output is correct
3	Correct	16 ms	1648 KB	Output is correct
4	Correct	18 ms	1684 KB	Output is correct
5	Correct	16 ms	1748 KB	Output is correct
6	Correct	17 ms	1688 KB	Output is correct
7	Correct	16 ms	1740 KB	Output is correct
8	Correct	17 ms	1620 KB	Output is correct
9	Correct	21 ms	1892 KB	Output is correct
10	Correct	20 ms	1916 KB	Output is correct
11	Correct	23 ms	1740 KB	Output is correct
12	Correct	48 ms	3180 KB	Output is correct
13	Correct	67 ms	4600 KB	Output is correct
14	Correct	100 ms	6100 KB	Output is correct
15	Correct	113 ms	7560 KB	Output is correct
16	Correct	151 ms	9108 KB	Output is correct
17	Correct	177 ms	10604 KB	Output is correct
18	Correct	189 ms	12052 KB	Output is correct
19	Correct	212 ms	13840 KB	Output is correct
20	Correct	181 ms	10572 KB	Output is correct