Submission #1100658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100658		stdfloat	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	226 ms	30244 KiB

jobs

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

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, d, m;
	cin >> n >> d >> m;

	pii p[m];
	for (int i = 0; i < m; i++) {
		cin >> p[i].ff; p[i].ff--; p[i].ss = i;
	}

	sort(p, p + m);

	int l = 0, r = m;
	vector<vector<int>> ans;
	while (l <= r) {
		int md = (l + r) >> 1;

		int cur = 0;
		vector<vector<int>> u(n);
		for (int i = 0; i < m; i++) {
			while (cur <= p[i].ff + d && (cur < p[i].ff || (int)u[cur].size() == md)) cur++;
		
			if (cur > p[i].ff + d) {
				cur = -1; break;
			}

			u[cur].push_back(p[i].ss);
		}

		if (!~cur) l = md + 1;
		else {
			ans = u;
			r = md - 1;
		}
	}

	cout << l << '\n';
	for (auto i : ans) {
		for (auto j : i)
			cout << j + 1 << ' ';
		cout << "0\n";
	}
}

• Subtask 1: 100 / 100