제출 #504374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
504374		ac2hu	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	237 ms	14148 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
pair<int,int> a[M];
int n,d,m;
bool check(int mid){
	int ans = 0;
	int k = 1;
	for(int i = 0;i<m;i+=mid){
		if(a[i].first > k){
			k++;
			i -= mid;
			continue;
		}
		ans = max(ans,k - a[i].first);
		k++;	
	}
	// cout << mid << " " << k << " " << ans << "\n";
	if(ans > d )//|| k > n - d)
		return false;
	else 
		return true;
}
signed main(){
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> d >> m;
	for(int i =0;i<m;i++){
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a,a + m);
	// for(int i = 0;i<m;i++)
	// 	cout << a[i].first << " ";
	// cout << "\n";
	int l = (m + n - 1)/n ,r = m;
	while(l < r){
		int mid = (l + r - 1)/2;
		if(check(mid))
			r = mid;
		else 
			l = mid + 1;
	}
	cout << l << "\n";
	int idx = -1;
	for(int i = 0;i<n;i++){
		if(idx == m - 1)
			cout << 0 << "\n";
		else{
			int j;
			int temp = idx;
			for(j = temp + 1;j<min(temp + l + 1, m);j++){
				idx = j;
				cout << a[idx].second  + 1 << " ";
			}
			cout << 0 << "\n";
		}
	}
	assert(idx == m - 1);
}

• Subtask 1: 100 / 100