Submission #914887

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914887	2024-01-22T20:15:35 Z	tvladm2009	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	189 ms	17236 KB

jobs

#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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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