oj.uz

답안 #635628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635628 2022-08-26T14:03:19 Z nayhz Job Scheduling (CEOI12_jobs) C++17
100 / 100
 580 ms 26888 KB 
// 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

# 결과 실행 시간 메모리 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