Submission #944686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
944686	2024-03-13T03:28:36 Z	rocketsri	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	1000 ms	15040 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	2592 KB	Output is correct
2	Correct	59 ms	2596 KB	Output is correct
3	Correct	59 ms	2580 KB	Output is correct
4	Correct	59 ms	2564 KB	Output is correct
5	Correct	59 ms	2596 KB	Output is correct
6	Correct	59 ms	2632 KB	Output is correct
7	Correct	65 ms	2632 KB	Output is correct
8	Correct	59 ms	2604 KB	Output is correct
9	Correct	151 ms	2628 KB	Output is correct
10	Correct	147 ms	2732 KB	Output is correct
11	Correct	192 ms	2632 KB	Output is correct
12	Incorrect	457 ms	4924 KB	Output isn't correct
13	Correct	706 ms	10384 KB	Output is correct
14	Incorrect	994 ms	10776 KB	Output isn't correct
15	Execution timed out	1067 ms	12104 KB	Time limit exceeded
16	Execution timed out	1061 ms	12080 KB	Time limit exceeded
17	Execution timed out	1058 ms	14840 KB	Time limit exceeded
18	Execution timed out	1039 ms	14720 KB	Time limit exceeded
19	Execution timed out	1074 ms	15040 KB	Time limit exceeded
20	Execution timed out	1048 ms	14772 KB	Time limit exceeded