제출 #1325335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325335		crispxx	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	173 ms	13868 KiB

jobs

#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;
		d[i][0]--;
	}
	
	sort(d.begin(), d.end());
	
	auto check = [&](int x) {
		for(int i = 0, j = 0; i < N && j < M; i++) {
			for(int it = 0; it < x && j < M && d[j][0] <= i; it++, j++) {
				if(i - d[j][0] > D) return false;
			}
		}
		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';
	
	for(int i = 0, j = 0; i < N; i++) {
		for(int it = 0; it < l && j < M && d[j][0] <= i; it++, j++) {
			cout << d[j][1] + 1 << ' ';
		}
		cout << 0 << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

• Subtask 1: 100 / 100