Submission #670425

#TimeUsernameProblemLanguageResultExecution timeMemory
670425asdf334Job Scheduling (CEOI12_jobs)C++17
100 / 100
253 ms17648 KiB
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int N, D, M; cin >> N >> D >> M;
	map<int, vector<int>> vals;
	for (int i = 1; i <= M; ++i) {
		int num; cin >> num;
		vals[num].push_back(i);
	}
	int left = 1; int right = 1e6;
	while (left < right) {
		int mid = left + (right - left) / 2;
		int day = 1; int curr = 0; int del = 0;
		for (auto val : vals) {
			if (day < val.first) {
				day = val.first; curr = 0;
			}
			for (int i = 0; i < sz(val.second); ++i) {
				if (curr < mid) {
					++curr; 
				} else {
					++day; curr = 1;
				}
				del = max(del, day - val.first);
			}
		} 
		if (del > D) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	cout << left << '\n';
	int ctr = 0; vector<vector<int>> ans(N);
	for (auto val : vals) {
		for (int num : val.second) {
			if (sz(ans[ctr]) >= left) ++ctr;
			ans[ctr].push_back(num);
		}
	}
	for (vector<int> day : ans) {
		for (int req : day) {
			cout << req << " ";
		}
		cout << 0 << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...