Submission #1269710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269710		WH8	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	214 ms	28412 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'

signed main(){
	int n,d,m;cin>>n>>d>>m;
	vector<vector<int>> v(n+1);
	for(int i=1;i<=m;i++){
		int d;cin>>d;
		v[d].pb(i);
	}
	int l=0, r=1000000,mac;
	while(r-l>1){
		mac=(l+r)/2;
		vector<int> use(n+1, 0), rem(n+1,0);
		for(int i=1;i<=n;i++)rem[i]=v[i].size();
		int usep=0;
		bool ok=true;
		for(int i=1;i<=n;i++){
			usep=max(usep, i);
			while(rem[i] and usep<=i+d){
				int take=min(rem[i], mac-use[usep]);
				use[usep]+=take;
				rem[i]-=take;
				if(use[usep]==mac)usep++;
			}
			if(rem[i] and usep > i+d){
				ok=false;
				break;
			}
		}
		//~ printf("with %lld machines, use is \n", mac);
		//~ for(int i=1;i<=n;i++){
			//~ cout<<use[i]<<" ";
		//~ }
		//~ cout<<endl;
		if(ok){
			r=mac;
		}
		else l=mac;
	}
	cout<<r<<"\n";
	vector<vector<int>> ans(n+1);
	int usep=1;
	for(int i=1;i<=n;i++){
		usep=max(usep, i);
		while(!v[i].empty()){
			ans[usep].pb(v[i].back());
			v[i].pop_back();
			if((int)ans[usep].size()>=r)usep++;
		}
	}
	for(int i=1;i<=n;i++){
		for(auto it:ans[i])cout<<it<<" ";
		cout<<"0\n";
	}
			
}

• Subtask 1: 100 / 100