답안 #914887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914887 2024-01-22T20:15:35 Z tvladm2009 Job Scheduling (CEOI12_jobs) C++17
100 / 100
189 ms 17236 KB
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	int days, delay, n;
	cin >> days >> delay >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<int> ord(n);
	iota(all(ord), 0);
	sort(all(ord), [&](int x, int y) {
		return a[x] < a[y];
	});
	auto check = [&](int x) {
		int pos = 0;
		for (int i = 1; i <= days; i++) {
			int today = 0;
			while (today < x && pos < n) {
				int cand = a[ord[pos]];
				if (i < cand) {
					break;
				}
				if (i > cand + delay) {
					return false;
				}
				pos++;
				today++;
			}
		}
		return pos == n;
	};
	int l = 1, r = n, sol = -1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (check(m)) {
			r = m - 1;
			sol = m;
		} else {
			l = m + 1;
		}
	}
	cout << sol << '\n';
	int pos = 0;
	for (int i = 1; i <= days; i++) {
		int today = 0;
		while (today < sol && pos < n) {
			int cand = a[ord[pos]];
			if (i < cand) {
				break;
			}
			cout << ord[pos] + 1 << ' ';
			pos++;
		}
		cout << 0 << '\n';
	}
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2136 KB Output is correct
2 Correct 16 ms 2140 KB Output is correct
3 Correct 13 ms 2136 KB Output is correct
4 Correct 13 ms 1996 KB Output is correct
5 Correct 13 ms 2136 KB Output is correct
6 Correct 13 ms 2140 KB Output is correct
7 Correct 13 ms 1876 KB Output is correct
8 Correct 13 ms 2140 KB Output is correct
9 Correct 23 ms 2140 KB Output is correct
10 Correct 20 ms 2140 KB Output is correct
11 Correct 18 ms 2088 KB Output is correct
12 Correct 38 ms 3928 KB Output is correct
13 Correct 59 ms 5600 KB Output is correct
14 Correct 89 ms 8024 KB Output is correct
15 Correct 103 ms 9384 KB Output is correct
16 Correct 134 ms 11856 KB Output is correct
17 Correct 154 ms 13652 KB Output is correct
18 Correct 168 ms 14932 KB Output is correct
19 Correct 189 ms 17236 KB Output is correct
20 Correct 151 ms 13804 KB Output is correct