Submission #670425

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670425	2022-12-09T01:47:08 Z	asdf334	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	253 ms	17648 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int N, D, M; cin >> N >> D >> M;
	map<int, vector<int>> vals;
	for (int i = 1; i <= M; ++i) {
		int num; cin >> num;
		vals[num].push_back(i);
	}
	int left = 1; int right = 1e6;
	while (left < right) {
		int mid = left + (right - left) / 2;
		int day = 1; int curr = 0; int del = 0;
		for (auto val : vals) {
			if (day < val.first) {
				day = val.first; curr = 0;
			}
			for (int i = 0; i < sz(val.second); ++i) {
				if (curr < mid) {
					++curr; 
				} else {
					++day; curr = 1;
				}
				del = max(del, day - val.first);
			}
		} 
		if (del > D) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	cout << left << '\n';
	int ctr = 0; vector<vector<int>> ans(N);
	for (auto val : vals) {
		for (int num : val.second) {
			if (sz(ans[ctr]) >= left) ++ctr;
			ans[ctr].push_back(num);
		}
	}
	for (vector<int> day : ans) {
		for (int req : day) {
			cout << req << " ";
		}
		cout << 0 << '\n';
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2508 KB	Output is correct
2	Correct	19 ms	2508 KB	Output is correct
3	Correct	18 ms	2616 KB	Output is correct
4	Correct	17 ms	2612 KB	Output is correct
5	Correct	18 ms	2572 KB	Output is correct
6	Correct	17 ms	2636 KB	Output is correct
7	Correct	17 ms	2596 KB	Output is correct
8	Correct	19 ms	2544 KB	Output is correct
9	Correct	25 ms	4628 KB	Output is correct
10	Correct	25 ms	4664 KB	Output is correct
11	Correct	25 ms	2132 KB	Output is correct
12	Correct	47 ms	3736 KB	Output is correct
13	Correct	76 ms	6628 KB	Output is correct
14	Correct	145 ms	9680 KB	Output is correct
15	Correct	119 ms	8624 KB	Output is correct
16	Correct	211 ms	12044 KB	Output is correct
17	Correct	239 ms	16716 KB	Output is correct
18	Correct	184 ms	14764 KB	Output is correct
19	Correct	216 ms	17648 KB	Output is correct
20	Correct	253 ms	16764 KB	Output is correct