Submission #944686

#	Time	Username	Problem	Language	Result	Execution time	Memory
944686		rocketsri	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	1074 ms	15040 KiB

jobs

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

int main() {
	int n, d, m; cin >> n >> d >> m;

	vector<int> og(m);
	for(int i=0; i<m; i++) {
		cin >> og[i];
	}

	int l=1, r=m, ans=-1;
	while(l <= r) {
		priority_queue<int, vector<int>, greater<int>> jobs;
		for(int i=0; i<m; i++) {
			jobs.push(og[i]);
		}

		int mid = (l+r)/2;

		int curr=1;
		bool fin=false, ok=true;

		while(curr <= n) {
			for(int j=0; j<mid; j++) {
				if(jobs.empty()) {
					fin=true;
					break;
				}

				if(jobs.top() > curr) {
					curr = jobs.top()-1;
					break;
				}

				int job = jobs.top(); jobs.pop();
				if(curr-job > d) {
					ok=false;
					break;
				}
			}
			curr++;

			if(fin || !ok) break;
		}

		if(fin && ok) {
			ans = mid;
			r = mid-1;
		}
		else {
			l = mid+1;
		}
	}

	cout << ans << "\n";

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> jobs;
	for(int i=0; i<m; i++) {
		jobs.push({og[i], i+1});
	}

	int curr=1; bool fin=false;
	while(curr <= n) {
		for(int j=0; j<ans; j++) {
			if(jobs.empty()) {
				fin=true;
				break;
			}

			if(jobs.top().first > curr) {
				for(int wait=curr; wait<=jobs.top().first-2; wait++) {
					cout << "0\n";
				}
				curr = jobs.top().first-1;
				break;
			}

			cout << jobs.top().second << " ";
			jobs.pop();
		}

		curr++;
		cout << "0\n";

		if(fin) break;
	}
	if(fin) {
		while(curr <= n) {
			cout << "0\n";
			curr++;
		}
	}
}

• Subtask 1: 60 / 100