Submission #693480

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
693480	2023-02-03T04:05:52 Z	ojuzuser12	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	316 ms	13760 KB

jobs

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N, D, M; cin >> N >> D >> M;
    vector<pair<int, int>> jobs(M);
    for(int i = 0; i < M; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i;
    }
    sort(jobs.begin(), jobs.end());
    long long l = 1, r = M, mid;
    while(l < r) {
        mid = (l + r) / 2;
        bool works = ((M + mid - 1) / mid <= N);
        int i = 0;
        for(long long d = 0; d < N; d++) {
            for(long long c = 0; c < mid; c++) {
                if(d + 1 < jobs[i].first) break;
                if(i >= M) break;
                if(d + 1 - jobs[i].first > D) {
                    works = false;
                    break;
                }
                i++;
            }
            if(!works) break;
        }
        if(works) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << r << '\n';
    int i = 0;
    for(long long d = 0; d < N; d++) {
        for(long long c = 0; c < r; c++) {
            if(d + 1 < jobs[i].first) break;
            if(i >= M) break;
            cout << jobs[i].second + 1 << ' ';
            i++;
        }
        cout << 0 << '\n';
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	1632 KB	Output is correct
2	Correct	22 ms	1628 KB	Output is correct
3	Correct	19 ms	1632 KB	Output is correct
4	Correct	17 ms	1668 KB	Output is correct
5	Correct	19 ms	1620 KB	Output is correct
6	Correct	17 ms	1620 KB	Output is correct
7	Correct	18 ms	1620 KB	Output is correct
8	Correct	19 ms	1692 KB	Output is correct
9	Correct	36 ms	1836 KB	Output is correct
10	Correct	40 ms	1860 KB	Output is correct
11	Correct	32 ms	1684 KB	Output is correct
12	Correct	56 ms	3112 KB	Output is correct
13	Correct	96 ms	4584 KB	Output is correct
14	Correct	114 ms	6128 KB	Output is correct
15	Correct	155 ms	7584 KB	Output is correct
16	Correct	196 ms	9100 KB	Output is correct
17	Correct	229 ms	10548 KB	Output is correct
18	Correct	269 ms	12084 KB	Output is correct
19	Correct	316 ms	13760 KB	Output is correct
20	Correct	201 ms	10528 KB	Output is correct