Submission #552014

#	Time	Username	Problem	Language	Result	Execution time	Memory
552014		acatmeowmeow	Job Scheduling (CEOI12_jobs)	C++11	90 / 100	406 ms	39500 KiB

jobs

#include <bits/stdc++.h>

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

using namespace std;

#define int long long 

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: 90 / 100