Submission #682829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
682829	2023-01-17T05:28:09 Z	mrkhan2000	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	257 ms	20248 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	23 ms	2516 KB	Output is correct
2	Correct	18 ms	2500 KB	Output is correct
3	Correct	23 ms	2644 KB	Output is correct
4	Correct	18 ms	2644 KB	Output is correct
5	Correct	18 ms	2508 KB	Output is correct
6	Correct	18 ms	2644 KB	Output is correct
7	Correct	18 ms	2504 KB	Output is correct
8	Correct	19 ms	2616 KB	Output is correct
9	Correct	25 ms	4804 KB	Output is correct
10	Correct	27 ms	4804 KB	Output is correct
11	Correct	33 ms	2160 KB	Output is correct
12	Correct	56 ms	4188 KB	Output is correct
13	Correct	95 ms	6772 KB	Output is correct
14	Correct	129 ms	9060 KB	Output is correct
15	Correct	141 ms	9632 KB	Output is correct
16	Correct	192 ms	12044 KB	Output is correct
17	Correct	232 ms	15972 KB	Output is correct
18	Correct	226 ms	16448 KB	Output is correct
19	Correct	257 ms	20248 KB	Output is correct
20	Correct	229 ms	16020 KB	Output is correct