Submission #974787

#TimeUsernameProblemLanguageResultExecution timeMemory
974787vjudge1Job Scheduling (CEOI12_jobs)C++17
0 / 100
425 ms17408 KiB
#include<iostream>
#include<algorithm>
using namespace std;

int n, d, m; // avalible days, max delay, job count
pair<int, int> arrive[1000001]; // when the jobs come in

bool isok(int machines) {
	int current = 0;
	for (int i = 1; i <= n; i++) {
		int machines_left = machines;
		while (machines_left > 0 && current < m && arrive[i].first <= i) {
			if (i - arrive[i].first >= d) {
				return false;
			}

			machines_left--;
			current++;
		}
	}

	return current == m; // can complete all jobs
}

int main() {
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++) {
		cin >> arrive[i].first;
		arrive[i].second = i + 1;
	}

	sort(arrive, arrive + m);

	int left = 1, right = m;
	int ans = 1;

	while (left <= right) {
		int mid = (left + right) / 2; // bsearch for how many machines needed
		if (isok(mid)) {
			ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}

	int current = 0;
	for (int i = 1; i <= n; i++) {
		int machines_left = ans;
		while (machines_left > 0 && current < m && arrive[i].first <= i) {
			cout << arrive[current].second << " ";

			machines_left--;
			current++;
		}

		cout << 0 << endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...