Submission #1199452

#TimeUsernameProblemLanguageResultExecution timeMemory
1199452orgiloogiiJob Scheduling (CEOI12_jobs)C++20
100 / 100
228 ms13824 KiB
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	int n, d, m;
	cin >> n >> d >> m;
	vector <pair <int, int>> reg(m + 1);
	for (int i = 1;i <= m;i++) {
		cin >> reg[i].first;
		reg[i].second = i;
	}
	sort(reg.begin(), reg.end());
	int l = 1, r = m;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		bool pos = true;
		int day = 1;
		for (int i = 1;i <= m;) {
			int cnt = mid;
			while (cnt && i <= m) {
				if (reg[i].first > day) break;
				if (reg[i].first + d < day) {
					pos = false;
					break;
				}
				i++;
				cnt--;
			}
			if (!pos) break;
			day++;
		}
		if (pos) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	cout << r << endl;
	bool pos = true;
	int day = 1;
	int p = 1;
	for (int i = 1;i <= m;) {
		int cnt = r;
		while (cnt && i <= m) {
			if (reg[i].first > day) break;
			cout << reg[i].second << " ";
			i++;
			cnt--;
		}
		cout << 0 << endl;
		p++;
		day++;
	}
	for (;p <= n;p++) {
		cout << 0 << endl;
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...