Submission #748645

#	Time	Username	Problem	Language	Result	Execution time	Memory
748645		mariowong	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	279 ms	14836 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
 
int n,d,m,l,r,mid,ct,pt,now;
pair <int,int> a[1000005]; 	
bool ok;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> d >> m;
	for (int i=1;i<=m;i++){
		cin >> a[i].first;
		a[i].second=i;
	}
	sort(a+1,a+1+m);
	l=1; r=m; 
	while (l < r){
		mid=(l+r)/2; ct=0;
		ok=true; pt=0;
		for (int i=1;i<=n;i++){
			now=0;
			while (now < mid && pt+1 <= m && a[pt+1].first <= i){
				pt++; now++;
				if (i > a[pt].first+d){
					pt=-1;
					goto out;
				}
			}
		} 
		out:;
		if (pt == m)
		r=mid;
		else
		l=mid+1;
	}
	cout << l << "\n"; pt=0;
	for (int i=1;i<=n;i++){
		now=0;
		while (now < l && pt+1 <= m && a[pt+1].first <= i){
			pt++; now++;
			cout << a[pt].second << " "; 
			if (i > a[pt].first+d){
				pt=-1;
				goto out;
			}
		}
		cout << "0\n";
	} 
	return 0;
}	

• Subtask 1: 100 / 100