Submission #504345

#	Time	Username	Problem	Language	Result	Execution time	Memory
504345		ac2hu	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	216 ms	13872 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){
		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: 55 / 100