답안 #652958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652958	2022-10-25T09:41:53 Z	try_to_reach_next_rank	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	408 ms	26424 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;

pair<bool, vector<vi>> isFeasible(const vector<pi> &jobs, int machineCount)
{
	vector<vi> schedule(N);
	int reqNum = 0;
	for (int day = 1; day <= N; day++)
	{
		for (int j = 0; j < machineCount; j++)
		{
			if (jobs[reqNum].first > day)
				break;
			if (jobs[reqNum].first + D >= day)
				schedule[day - 1].push_back(jobs[reqNum++].second);
			else
				return mp(false, schedule);
			if (reqNum == M)
				return mp(true, schedule);
		}
	}
	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;
		pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
		if (curResult.first)
		{
			r = machineNum;
			result = curResult.second;
		}
		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	2980 KB	Output is correct
2	Correct	30 ms	3016 KB	Output is correct
3	Correct	33 ms	2968 KB	Output is correct
4	Correct	32 ms	3060 KB	Output is correct
5	Correct	34 ms	2968 KB	Output is correct
6	Correct	33 ms	2992 KB	Output is correct
7	Correct	32 ms	3004 KB	Output is correct
8	Correct	33 ms	3052 KB	Output is correct
9	Correct	97 ms	9632 KB	Output is correct
10	Correct	93 ms	9692 KB	Output is correct
11	Correct	47 ms	2748 KB	Output is correct
12	Correct	82 ms	5000 KB	Output is correct
13	Correct	122 ms	8568 KB	Output is correct
14	Correct	194 ms	10852 KB	Output is correct
15	Correct	218 ms	10992 KB	Output is correct
16	Correct	264 ms	16112 KB	Output is correct
17	Correct	313 ms	18768 KB	Output is correct
18	Correct	333 ms	23280 KB	Output is correct
19	Correct	408 ms	26424 KB	Output is correct
20	Correct	309 ms	18856 KB	Output is correct