Submission #635628

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
635628	2022-08-26T14:03:19 Z	nayhz	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	580 ms	26888 KB

jobs

// CEOI 2012 Dau 1 Job Scheduling
#include <bits/stdc++.h>
#define pii pair<int, int>

#define vi vector<int>
#define vpii vector<pair<int, int>>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;

/*
>>>>>>>>>>>>>>>>>>>>>>>>>>END OF TEMPLATE HEADER<<<<<<<<<<<<<<<<<<<<<<<<
*/

void solve () {
	int n, d, m; cin >> n >> d >> m;
	vpii a(m);
	for (int i = 0; i < m; i++) {cin >> a[i].fi; a[i].se = i + 1;}
	sort(all(a));

	vector<vi> ans(n), ret(n);
	int l = 1, r = m, mid, day, i, cnt;

	function<bool()> check = [&] () {
		for (int i = 0; i < n; i++) ret[i].clear();
		cnt = 0;

		for (day = 1; day <= n; day++) {
			for (i = 0; i < mid; i++) {
				if (a[cnt].fi > day) break;

				if (a[cnt].fi + d >= day){ 
					ret[day - 1].pb(a[cnt++].se);
				}
				else return false;

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

	bool temp;
	while (l < r) {
		mid = l + ((r - l) >> 1);

		temp = check();
		if (temp) {
			r = mid, ans = ret;
		} else l = mid + 1;
	}

	cout << l << '\n';
	for (i = 0; i < n; i++) {
		for (int j = 0; j < (int)ans[i].size(); j++) cout << ans[i][j] << ' ';
		cout << "0\n";
	}
}

signed main () {
	solve();
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	3012 KB	Output is correct
2	Correct	49 ms	3004 KB	Output is correct
3	Correct	42 ms	2972 KB	Output is correct
4	Correct	41 ms	2976 KB	Output is correct
5	Correct	41 ms	3020 KB	Output is correct
6	Correct	41 ms	3004 KB	Output is correct
7	Correct	41 ms	3004 KB	Output is correct
8	Correct	51 ms	2972 KB	Output is correct
9	Correct	65 ms	7488 KB	Output is correct
10	Correct	67 ms	7484 KB	Output is correct
11	Correct	57 ms	2672 KB	Output is correct
12	Correct	119 ms	5196 KB	Output is correct
13	Correct	180 ms	8136 KB	Output is correct
14	Correct	238 ms	11416 KB	Output is correct
15	Correct	268 ms	12652 KB	Output is correct
16	Correct	361 ms	16188 KB	Output is correct
17	Correct	447 ms	20236 KB	Output is correct
18	Correct	523 ms	20476 KB	Output is correct
19	Correct	580 ms	26888 KB	Output is correct
20	Correct	437 ms	20248 KB	Output is correct