Submission #644750

#	Time	Username	Problem	Language	Result	Execution time	Memory
644750		Zflop	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	433 ms	26404 KiB

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;
		jobs[i] = mp(day, i + 1);
	}
	sort(all(jobs));

	vector<vi> result;
	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 / 100