Submission #760085

#	Time	Username	Problem	Language	Result	Execution time	Memory
760085		lukehsiao	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	112 ms	16756 KiB

jobs

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

const int mxN = 1e5+1;

int n, D, m;
vector<int> days[mxN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> D >> m;
	for (int i=1, a; i<=m; ++i) {
		cin >> a;
		days[a].push_back(i);
	}

	int lo = 1, hi = 1e6;
	while (lo < hi) {
		int mid = (lo+hi)/2;
		bool works = true;
		// cnt, deadline
		queue<pair<int, int>> q;
		for (int i=1; i<=n && works; ++i) {
			int left = mid;
			if (days[i].size())
				q.push({(int)days[i].size(), i+D});
			while (!q.empty() && left) {
				if (i > q.front().second) {
					works = false;
					break;
				}
				int sub = min(left, q.front().first);
				left -= sub;
				q.front().first -= sub;
				if (!q.front().first)
					q.pop();
			}
		}

		if (works && q.empty())
			hi = mid;
		else
			lo = mid+1;
	}

	cout << lo << '\n';

	queue<int> q;
	for (int i=1; i<=n; ++i) {
		for (const int &x : days[i])
			q.push(x);
		int left = lo;
		while (!q.empty() && left) {
			cout << q.front() << ' ';
			q.pop();
			--left;
		}
		cout << "0\n";
	}
}

• Subtask 1: 100 / 100