Submission #1182935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182935		sosuke	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	357 ms	26448 KiB

jobs

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

int main() {
	int n, d, m;
	std::cin >> n >> d >> m;
	std::vector<std::array<int, 2>> jobs(m);
	for (int i = 0; i < m; i++) {
		int day;
		std::cin >> day;
		jobs[i] = {day, i + 1};
	}

	std::sort(begin(jobs), end(jobs));
	std::vector<std::vector<int>> res;

	auto is_feasible = [&] (int machine_count) -> std::pair<bool, std::vector<std::vector<int>>> {
		std::vector<std::vector<int>> schedule(n);
		int req_num = 0;

		for (int day = 1; day <= n; day++) {
			for (int j = 0; j < machine_count; j++) {
				if (jobs[req_num][0] > day) {
					break;
				}
				if (jobs[req_num][0] + d >= day) {
					schedule[day - 1].push_back(jobs[req_num++][1]);
				} else {
					return {false, schedule};
				}

				if (req_num == m) {
					return {true, schedule};
				}
			}
		}
		return {false, schedule};
	};

	int lo = 1, hi = m;
	while (lo < hi) {
		int machine_num = (lo + hi) / 2;
		
		std::pair<bool, std::vector<std::vector<int>>> curr_result = is_feasible(machine_num);

		if (curr_result.first) {
			hi = machine_num;
			res = curr_result.second;
		} else {
			lo = machine_num + 1;
		}
	}

	std::cout << lo << '\n';
	for (int i = 0; i < n; i++) {
		for (int idx : res[i]) {
			std::cout << idx << " ";
		}
		std::cout << 0 << '\n';
	}
}

• Subtask 1: 100 / 100