oj.uz

Submission #760085

# Submission time Handle Problem Language Result Execution time Memory
760085 2023-06-17T07:22:25 Z lukehsiao Job Scheduling (CEOI12_jobs) C++14
100 / 100
 112 ms 16756 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e5+1;

int n, D, m;
vector<int> days[mxN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> D >> m;
	for (int i=1, a; i<=m; ++i) {
		cin >> a;
		days[a].push_back(i);
	}

	int lo = 1, hi = 1e6;
	while (lo < hi) {
		int mid = (lo+hi)/2;
		bool works = true;
		// cnt, deadline
		queue<pair<int, int>> q;
		for (int i=1; i<=n && works; ++i) {
			int left = mid;
			if (days[i].size())
				q.push({(int)days[i].size(), i+D});
			while (!q.empty() && left) {
				if (i > q.front().second) {
					works = false;
					break;
				}
				int sub = min(left, q.front().first);
				left -= sub;
				q.front().first -= sub;
				if (!q.front().first)
					q.pop();
			}
		}

		if (works && q.empty())
			hi = mid;
		else
			lo = mid+1;
	}

	cout << lo << '\n';

	queue<int> q;
	for (int i=1; i<=n; ++i) {
		for (const int &x : days[i])
			q.push(x);
		int left = lo;
		while (!q.empty() && left) {
			cout << q.front() << ' ';
			q.pop();
			--left;
		}
		cout << "0\n";
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4300 KB Output is correct
2 Correct 13 ms 4312 KB Output is correct
3 Correct 13 ms 4364 KB Output is correct
4 Correct 13 ms 4396 KB Output is correct
5 Correct 13 ms 4396 KB Output is correct
6 Correct 13 ms 4336 KB Output is correct
7 Correct 14 ms 4396 KB Output is correct
8 Correct 17 ms 4372 KB Output is correct
9 Correct 16 ms 4356 KB Output is correct
10 Correct 17 ms 4308 KB Output is correct
11 Correct 14 ms 4176 KB Output is correct
12 Correct 26 ms 5708 KB Output is correct
13 Correct 38 ms 7928 KB Output is correct
14 Correct 60 ms 10008 KB Output is correct
15 Correct 60 ms 10828 KB Output is correct
16 Correct 85 ms 13496 KB Output is correct
17 Correct 104 ms 15800 KB Output is correct
18 Correct 96 ms 15556 KB Output is correct
19 Correct 112 ms 16756 KB Output is correct
20 Correct 102 ms 15796 KB Output is correct