Submission #514920

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
514920	2022-01-18T19:39:46 Z	thiago_bastos	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	276 ms	20104 KB

jobs

#include "bits/stdc++.h"

using namespace std;
 
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

void solve() {

	int n, d, m;

	cin >> n >> d >> m;

	vector<ii> job(m);

	for(int i = 0; i < m; ++i) {
		cin >> job[i].first;
		job[i].second = i + 1;
	}

	sort(job.begin(), job.end());

	int lo = 1, hi = m;

	while(lo < hi) {
		int mid = (lo + hi) / 2, j = 0;
		bool ok = true;
		for(int i = 1; i <= n && j < m; ++i) {
			int k = j;
			while(k < m && k - j < mid && job[k].first <= i) {
				ok = ok && i - job[k].first <= d;
				++k;
			}
			j = k;
		}
		if(ok && j == m) hi = mid;
		else lo = mid + 1;
	}

	cout << hi << '\n';

	vector<vector<int>> sch(n + 1);

	for(int i = 1, j = 0; i <= n; ++i) {
		int k = j;
		while(k < m && k - j < hi && job[k].first <= i) sch[i].push_back(job[k++].second);
		j = k;
	}

	for(int i = 1; i <= n; ++i) {
		for(int id : sch[i]) cout << id << ' ';
		cout << "0\n";
	}
}
 
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	2388 KB	Output is correct
2	Correct	17 ms	2428 KB	Output is correct
3	Correct	18 ms	2380 KB	Output is correct
4	Correct	20 ms	2388 KB	Output is correct
5	Correct	18 ms	2380 KB	Output is correct
6	Correct	23 ms	2484 KB	Output is correct
7	Correct	18 ms	2460 KB	Output is correct
8	Correct	24 ms	2380 KB	Output is correct
9	Correct	28 ms	4716 KB	Output is correct
10	Correct	35 ms	4672 KB	Output is correct
11	Correct	26 ms	2136 KB	Output is correct
12	Correct	52 ms	4184 KB	Output is correct
13	Correct	75 ms	6620 KB	Output is correct
14	Correct	117 ms	8960 KB	Output is correct
15	Correct	139 ms	9596 KB	Output is correct
16	Correct	160 ms	11924 KB	Output is correct
17	Correct	197 ms	16028 KB	Output is correct
18	Correct	207 ms	16424 KB	Output is correct
19	Correct	276 ms	20104 KB	Output is correct
20	Correct	193 ms	15896 KB	Output is correct