Submission #1201149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201149		shadowlord	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	305 ms	26980 KiB

jobs

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

using std::vector;

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

	/*
	 * we sort the jobs by the request date in ascending order
	 * so that we can test them using isFeasible() in linear time whether they
	 * can be done in given time using a certain amount of machines
	 */
	std::sort(begin(jobs), end(jobs));
	vector<vector<int>> res;

	/** @return true along with schedule if it feasible to finish the jobs otherwise
	 * false */
	auto is_feasible = [&](int machine_count) -> vector<vector<int>> {
		vector<vector<int>> schedule(n);
		int req_num = 0;

		/*
		 * we simulate from day 1 until the last day n
		 * we move to the next day if all the machines are used or
		 * there is no more job requests left on or before this day
		 */
		for (int day = 1; day <= n; day++) {
			for (int j = 0; j < machine_count; j++) {

				/*
				 * if all jobs before and on this day are finished,
				 * we can go to the next day, even if there are usable machines left
				 * we can determine that since the vector jobs is sorted
				 */
				if (jobs[req_num][0] > day) { break; }
				/*
				 * if the current date is before the deadline for the job
				 * we can add this job to the schedule and move to the next
				 * job request
				 */
				if (jobs[req_num][0] + d >= day) {
					schedule[day - 1].push_back(jobs[req_num++][1]);
				} else {  // otherwise, it is not feasible due to deadline
					return {};
				}

				/*
				 * if we have processed all the requests, we have found a
				 * feasible solution
				 */
				if (req_num == m) { return schedule; }
			}
		}

		/*
		 * if not all the requests can be processed within the given n days,
		 * then it is not feasible
		 */
		return {};
	};

	int lo = 1;
	int hi = m;
	while (lo < hi) {
		int machine_num = (lo + hi) / 2;

		/*
		 * test if the jobs would finish within the deadline
		 * using the current # of machines i.e., machine_num
		 */
		vector<vector<int>> curr_result = is_feasible(machine_num);

		/*
		 * if it's possible, we set the right bound as the tested
		 * machine number and save the current schedule
		 */
		if (!curr_result.empty()) {
			hi = machine_num;
			res = curr_result;
		} else {
			/*
			 * otherwise, we set the left bound to be the tested number + 1
			 * and test the next machine_num again
			 */
			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