Submission #552019

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
552019	2022-04-22T08:17:08 Z	acatmeowmeow	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	329 ms	27540 KB

jobs

#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

#	Verdict	Execution time	Memory	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