답안 #944686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944686 2024-03-13T03:28:36 Z rocketsri Job Scheduling (CEOI12_jobs) C++17
60 / 100
1000 ms 15040 KB
#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++;
		}
	}
}
# 결과 실행 시간 메모리 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