Submission #527739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527739	2022-02-18T06:45:11 Z	_karan_gandhi	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	338 ms	20160 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

void solve() {
	int n, d, m; cin >> n >> d >> m;
	vector<pair<int, int>> arr(m); for (int i = 0; i < m; i++) cin >> arr[i].first;
	for (int i = 0; i < m; i++) arr[i].second = i + 1;
	sort(all(arr));

	auto possible = [&](int x) {
		// check if it is possible to complete the jobs with x machines
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < x; j++) {
				if (arr[cnt].first > i) {
					break;
				}

				if (arr[cnt].first + d >= i) {
					cnt++;
				} else {
					return false;
				}

				if (cnt == m) return true;
			}
		}

		return false;
	};

	// cout << pl(possible(2)) << endl;

	int hi = m, lo = 1;
	int ans = 0;
	while (hi >= lo) {
		int mid = (hi + lo) / 2;

		if (possible(mid)) {
			ans = mid;
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}


	cout << ans << endl;
	// find a way to get answer
	vector<vector<int>> days(n + 1);
	multiset<int> s;
	for (int i = 0; i < ans; i++) {
		// cout << pl(arr[i].second) << endl;
		s.insert(arr[i].first);
			days[arr[i].first - 1].push_back(arr[i].second);
	}

	for (int i = ans; i < m; i++) {
		int last = *s.begin();
		s.erase(s.find(last));
		s.insert(max(last + 1, arr[i].first));
		days[max(last + 1, arr[i].first) - 1].push_back(arr[i].second);
	}

	for (int i = 0; i < n; i++) {
		for (int a : days[i]) cout << a << ' ';
		cout << 0 << endl;
	}
}

int main() {
	// freopen("socdist.in", "r", stdin);
	// freopen("socdist.out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// int t; cin >> t;
	// while (t--)
		solve();

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	4804 KB	Output is correct
2	Correct	38 ms	4720 KB	Output is correct
3	Correct	39 ms	4804 KB	Output is correct
4	Correct	38 ms	4788 KB	Output is correct
5	Correct	41 ms	4812 KB	Output is correct
6	Correct	39 ms	4812 KB	Output is correct
7	Correct	39 ms	4824 KB	Output is correct
8	Correct	42 ms	4728 KB	Output is correct
9	Correct	49 ms	4968 KB	Output is correct
10	Correct	47 ms	4940 KB	Output is correct
11	Correct	34 ms	2128 KB	Output is correct
12	Correct	78 ms	4188 KB	Output is correct
13	Correct	111 ms	6728 KB	Output is correct
14	Correct	146 ms	8952 KB	Output is correct
15	Correct	203 ms	9592 KB	Output is correct
16	Correct	213 ms	11924 KB	Output is correct
17	Correct	261 ms	15816 KB	Output is correct
18	Correct	321 ms	16420 KB	Output is correct
19	Correct	338 ms	20160 KB	Output is correct
20	Correct	257 ms	15896 KB	Output is correct