답안 #674282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674282	2022-12-23T16:24:41 Z	thienbao1602	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	405 ms	26380 KB

jobs

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

#define all(x) begin(x), end(x)
#define mp make_pair

using pi = pair<int, int>;
using vi = vector<int>;

int N, D, M;

// test if it is possible to finish the jobs using given # of machines
// return: first: possible or not, second: if possible, the schedule for the jobs
pair<bool, vector<vi>> isFeasible(const vector<pi> &jobs, int machineCount)
{
	vector<vi> schedule(N);
	int reqNum = 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 < machineCount; 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[reqNum].first > 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[reqNum].first + D >= day)
				schedule[day - 1].push_back(jobs[reqNum++].second);
			// otherwise, it is not feasible due to deadline
			else
				return mp(false, schedule);

			// if we have processed all the requests, we have found a feasible sol
			if (reqNum == M)
				return mp(true, schedule);
		}
	}
	// if not all the requests can be processed within the given N days,
	// then it is not feasible
	return mp(false, schedule);
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);

	cin >> N >> D >> M;
	vector<pi> jobs(M);
	for (int i = 0; i < M; i++)
	{
		int day;
		cin >> day;
		// first: request date, second: index [1..M]
		jobs[i] = mp(day, i + 1);
	}
	// we sort the jobs by the request date in ascending order
	// sothat we can test them using isFeasible() in linear time whether they
	// can be done in given time using a certain amount of machines
	sort(all(jobs));

	vector<vi> result;
	// binary search on the number of machines for the minimum possible solution
	// left and right bound, l and r
	int l = 1, r = M;
	while (l < r)
	{
		int machineNum = (l + r) / 2;
		// test if the jobs would finish within the deadline
		// using the current # of machines, machineNum
		pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
		// if it's possible, we set the right bound as the tested machine number
		// and save the current schedule
		if (curResult.first)
		{
			r = machineNum;
			result = curResult.second;
		}
		// otherwise, we set the left bound to be the tested number + 1
		// and test the next machineNum again
		else
			l = machineNum + 1;
	}

	cout << l << "\n";
	for (int i = 0; i < N; i++)
	{
		for (int &idx : result[i])
			cout << idx << " ";
		cout << 0 << "\n";
	}
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	3108 KB	Output is correct
2	Correct	29 ms	3084 KB	Output is correct
3	Correct	30 ms	3120 KB	Output is correct
4	Correct	30 ms	3016 KB	Output is correct
5	Correct	35 ms	2968 KB	Output is correct
6	Correct	30 ms	2968 KB	Output is correct
7	Correct	29 ms	2972 KB	Output is correct
8	Correct	30 ms	3104 KB	Output is correct
9	Correct	75 ms	9652 KB	Output is correct
10	Correct	81 ms	9704 KB	Output is correct
11	Correct	38 ms	2740 KB	Output is correct
12	Correct	78 ms	4960 KB	Output is correct
13	Correct	106 ms	8580 KB	Output is correct
14	Correct	180 ms	10740 KB	Output is correct
15	Correct	199 ms	10980 KB	Output is correct
16	Correct	253 ms	16116 KB	Output is correct
17	Correct	320 ms	18816 KB	Output is correct
18	Correct	320 ms	23208 KB	Output is correct
19	Correct	405 ms	26380 KB	Output is correct
20	Correct	321 ms	18720 KB	Output is correct