Submission #838979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
838979	2023-08-28T12:13:05 Z	Peter_Peter	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	220 ms	23536 KB

jobs

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N, D, M;
	cin >> N >> D >> M;
	vector<int> A(M);
	for(int i = 0; i < M; i++) {
		cin >> A[i];
	}
	vector<int> order(M);
	iota(order.begin(), order.end(), 1);
	sort(order.begin(), order.end(), [&](int i, int j) -> bool { return A[i - 1] > A[j - 1]; });
	sort(A.begin(), A.end(), greater<int>());
	int lo = 1, hi = M;
	while(lo < hi) {
		int mid = lo + (hi - lo) / 2;
		int mx_d = 0, day = 1;
		vector<int> B = A;
		while(!B.empty()) {
			int mu = 0;
			while(mu < mid && !B.empty() && B.back() <= day) {
				mx_d = max(mx_d, day - B.back());
				B.pop_back();
				mu++;
			}
			day++;
		}
		if(mx_d <= D) {
			hi = mid;
		}
		else {
			lo = mid + 1;
		}
	}
	vector<vector<int>> ans(N);
	int day = 1;
	while(!A.empty()) {
		int mu = 0;
		while(mu < lo && !A.empty() && A.back() <= day) {
			ans[day - 1].push_back(order.back());
			A.pop_back();
			order.pop_back();
			mu++;
		}
		ans[day - 1].push_back(0);
		day++;
	}
	cout << lo << '\n';
	for(int i = 0; i < N; i++) {
		if(ans[i].empty()) {
			cout << "0\n";
			continue;
		}
		for(int j = 0; j < (int)ans[i].size(); j++) {
			cout << ans[i][j] << " \n"[j == (int)ans[i].size() - 1];
		}
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	2884 KB	Output is correct
2	Correct	15 ms	2824 KB	Output is correct
3	Correct	15 ms	2888 KB	Output is correct
4	Correct	15 ms	2836 KB	Output is correct
5	Correct	20 ms	2884 KB	Output is correct
6	Correct	15 ms	2880 KB	Output is correct
7	Correct	15 ms	2808 KB	Output is correct
8	Correct	15 ms	2892 KB	Output is correct
9	Correct	21 ms	5060 KB	Output is correct
10	Correct	21 ms	5064 KB	Output is correct
11	Correct	24 ms	2616 KB	Output is correct
12	Correct	47 ms	4920 KB	Output is correct
13	Correct	71 ms	7748 KB	Output is correct
14	Correct	107 ms	10924 KB	Output is correct
15	Correct	119 ms	11576 KB	Output is correct
16	Correct	160 ms	14896 KB	Output is correct
17	Correct	189 ms	19252 KB	Output is correct
18	Correct	191 ms	19380 KB	Output is correct
19	Correct	220 ms	23536 KB	Output is correct
20	Correct	195 ms	19220 KB	Output is correct