oj.uz

답안 #552019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552019 2022-04-22T08:17:08 Z acatmeowmeow Job Scheduling (CEOI12_jobs) C++11
100 / 100
 329 ms 27540 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

using namespace std;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, d, q;
	cin >> n >> d >> q;
	vector<vector<int>> day(n + 5), sol;
	for (int i = 1; i <= q; i++) {
		int x;
		cin >> x;
		day[x].push_back(i);
	}
	int l = 1, r = q, ans = q;
	while (l <= r) {
		int m = (l + r)/2;
		vector<vector<int>> res(n + 5);
		queue<pair<int, int>> pq;
		bool possible = true;
		for (int i = 1; i <= n; i++) {
			int machine = m;
			for (auto &v : day[i]) pq.push({i, v});
			while (machine && pq.size()) {
				int st = pq.front().first, indx = pq.front().second;
				pq.pop();
				if (i - st > d) possible = false;
				res[i].push_back(indx);
				machine--;
			}
		}
		if (possible && pq.empty()) ans = m, r = m - 1, sol = res;
		else l = m + 1;
	}
	cout << ans << '\n';
	for (int i = 1; i <= n; i++) {
		for (auto &v : sol[i]) cout << v << ' ';
		cout << 0 << '\n';
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 3740 KB Output is correct
2 Correct 32 ms 3720 KB Output is correct
3 Correct 33 ms 3660 KB Output is correct
4 Correct 30 ms 3748 KB Output is correct
5 Correct 30 ms 3724 KB Output is correct
6 Correct 33 ms 3732 KB Output is correct
7 Correct 31 ms 3636 KB Output is correct
8 Correct 31 ms 3760 KB Output is correct
9 Correct 59 ms 10124 KB Output is correct
10 Correct 61 ms 10284 KB Output is correct
11 Correct 35 ms 2872 KB Output is correct
12 Correct 66 ms 5504 KB Output is correct
13 Correct 98 ms 8904 KB Output is correct
14 Correct 176 ms 12204 KB Output is correct
15 Correct 168 ms 12356 KB Output is correct
16 Correct 257 ms 15680 KB Output is correct
17 Correct 306 ms 20584 KB Output is correct
18 Correct 287 ms 19820 KB Output is correct
19 Correct 329 ms 27540 KB Output is correct
20 Correct 313 ms 20660 KB Output is correct