Submission #1325319

#TimeUsernameProblemLanguageResultExecution timeMemory
1325319crispxxJob Scheduling (CEOI12_jobs)C++20
25 / 100
230 ms13712 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
	int N, D, M; cin >> N >> D >> M;
	
	vector<array<int, 2>> d(M);
	
	for(int i = 0; i < M; i++) {
		cin >> d[i][0];
		d[i][1] = i;
	}
	
	sort(d.begin(), d.end());
	
	auto check = [&](int x) {
		queue<int> q;
		for(int i = 0, j = 0; i < N && j < M; i++) {
			while(j < M && d[j][0] <= i + 1) {
				q.push(d[j][0]);
				j++;
			}
			for(int it = 0; it < x && !q.empty(); it++) {
				if((i + 1) - q.front() > D) return false;
				q.pop();
			}
		}
		return true;
	};
	
	int l = 1, r = M;
	
	while(l < r) {
		int mid = (l + r) >> 1;
		
		if(check(mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	
	cout << l << '\n';
	
	queue<int> q;
	
	for(int i = 0, j = 0; i < N; i++) {
		while(j < M && d[j][0] <= i + 1) {
			q.push(d[j][1]);
			j++;
		}
		for(int it = 0; it < l && !q.empty(); it++) {
			cout << q.front() + 1 << ' ';
			q.pop();
		}
		cout << 0 << '\n';
	}
	
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...