Submission #1120972

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1120972	2024-11-28T09:53:13 Z	classic	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	248 ms	23504 KB

jobs

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int numDay, limitDelay, numRequest;
	std::cin >> numDay >> limitDelay >> numRequest;
	std::vector<int> dayStartRequest(numRequest);
	for (int &day : dayStartRequest) {
		std::cin >> day;
	}
	std::vector<int> order(numRequest);
	iota(order.begin(), order.end(), 0);
	sort(order.begin(), order.end(), [&](int indexLeft, int indexRight) {
		return dayStartRequest[indexLeft] > dayStartRequest[indexRight];
	});
	sort(dayStartRequest.begin(), dayStartRequest.end(), std::greater<int>());
	int low = 1, high = numRequest, needMachine = high;
	while (low <= high) {
		int middle = low + ((high - low + 1) >> 1);
		int maxDelay = 0, day = 1;
		for (int index = numRequest - 1; index >= 0; ) {
			int machine = 0;
			while (index >= 0 && day >= dayStartRequest[index] && machine < middle) {
				maxDelay = std::max(maxDelay, day - dayStartRequest[index]);
				index--;
				machine++;
			}
			day++;
		}
		if (maxDelay <= limitDelay) {
			needMachine = middle;
			high = middle - 1;
		} else {
			low = middle + 1;
		}
	}
	std::cout << needMachine << '\n';
	std::vector<std::vector<int>> schedule(numDay);
	int day = 1;
	for (int index = numRequest - 1; index >= 0; ) {
		int machine = 0;
		while (index >= 0 && day >= dayStartRequest[index] && machine < needMachine) {
			schedule[day - 1].emplace_back(order[index] + 1);
			index--;
			machine++;
		}
		day++;
	}
	for (int day = 0; day < numDay; day++) {
		for (const int &index : schedule[day]) {
			std::cout << index << ' ';
		}
		std::cout << 0 << '\n';
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2900 KB	Output is correct
2	Correct	15 ms	2752 KB	Output is correct
3	Correct	16 ms	3068 KB	Output is correct
4	Correct	15 ms	2900 KB	Output is correct
5	Correct	15 ms	2900 KB	Output is correct
6	Correct	17 ms	2912 KB	Output is correct
7	Correct	16 ms	2900 KB	Output is correct
8	Correct	18 ms	2820 KB	Output is correct
9	Correct	26 ms	4948 KB	Output is correct
10	Correct	30 ms	4948 KB	Output is correct
11	Correct	23 ms	2644 KB	Output is correct
12	Correct	48 ms	4944 KB	Output is correct
13	Correct	77 ms	7788 KB	Output is correct
14	Correct	124 ms	11084 KB	Output is correct
15	Correct	142 ms	11656 KB	Output is correct
16	Correct	169 ms	14952 KB	Output is correct
17	Correct	216 ms	19280 KB	Output is correct
18	Correct	195 ms	19572 KB	Output is correct
19	Correct	248 ms	23504 KB	Output is correct
20	Correct	239 ms	19276 KB	Output is correct