oj.uz

Submission #1100658

# Submission time Handle Problem Language Result Execution time Memory
1100658 2024-10-14T11:50:31 Z stdfloat Job Scheduling (CEOI12_jobs) C++17
100 / 100
 226 ms 30244 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, d, m;
	cin >> n >> d >> m;

	pii p[m];
	for (int i = 0; i < m; i++) {
		cin >> p[i].ff; p[i].ff--; p[i].ss = i;
	}

	sort(p, p + m);

	int l = 0, r = m;
	vector<vector<int>> ans;
	while (l <= r) {
		int md = (l + r) >> 1;

		int cur = 0;
		vector<vector<int>> u(n);
		for (int i = 0; i < m; i++) {
			while (cur <= p[i].ff + d && (cur < p[i].ff || (int)u[cur].size() == md)) cur++;
		
			if (cur > p[i].ff + d) {
				cur = -1; break;
			}

			u[cur].push_back(p[i].ss);
		}

		if (!~cur) l = md + 1;
		else {
			ans = u;
			r = md - 1;
		}
	}

	cout << l << '\n';
	for (auto i : ans) {
		for (auto j : i)
			cout << j + 1 << ' ';
		cout << "0\n";
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3164 KB Output is correct
2 Correct 23 ms 3004 KB Output is correct
3 Correct 23 ms 3004 KB Output is correct
4 Correct 23 ms 3004 KB Output is correct
5 Correct 23 ms 2748 KB Output is correct
6 Correct 23 ms 3172 KB Output is correct
7 Correct 30 ms 3004 KB Output is correct
8 Correct 26 ms 3004 KB Output is correct
9 Correct 32 ms 7932 KB Output is correct
10 Correct 31 ms 7968 KB Output is correct
11 Correct 25 ms 3152 KB Output is correct
12 Correct 49 ms 5960 KB Output is correct
13 Correct 76 ms 9436 KB Output is correct
14 Correct 120 ms 13404 KB Output is correct
15 Correct 116 ms 14460 KB Output is correct
16 Correct 167 ms 18524 KB Output is correct
17 Correct 202 ms 23212 KB Output is correct
18 Correct 202 ms 23644 KB Output is correct
19 Correct 226 ms 30244 KB Output is correct
20 Correct 197 ms 19804 KB Output is correct