Submission #914887

#TimeUsernameProblemLanguageResultExecution timeMemory
914887tvladm2009Job Scheduling (CEOI12_jobs)C++17
100 / 100
189 ms17236 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...