Submission #875311

#	Time	Username	Problem	Language	Result	Execution time	Memory
875311		PM1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	394 ms	16724 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e6+5;
int n,m,d;
pair<int,int>a[mxn];
int main(){
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].fr;
		a[i].sc=i;
	}
	a[m+1].fr=1e9;
	sort(a+1,a+m+1);
	int l=0,r=m;
	while(r-l>1){
		//cout<<r<<" "<<l<<endl;
		int mid=(l+r)/2,p=1;
		for(int i=1;i<=n;i++){
			if(a[p].fr+d<i){
				break;
			}
			int cnt=0;
			while(cnt<mid && a[p].fr<=i){
				cnt++;
				p++;
			}
		}
		if(p>m){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	cout<<r<<endl;
	int p=1;
	for(int i=1;i<=n;i++){
		int cnt=0;
		while(cnt<r && a[p].fr<=i){
			cnt++;
			cout<<a[p].sc<<" ";
			p++;
		}
		cout<<0<<endl;
	}
}

• Subtask 1: 100 / 100