Submission #1280613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280613		yintercept	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	285 ms	11680 KiB

jobs

#include<bits/stdc++.h>
#include<vector>
using namespace std;
int ar[100004];
int tempar[100004];
int n,d,m;
vector<int> days[100004];

bool check(int mac);
void out(int ans);

int main(){
	cin>>n>>d>>m;
	int l,r,temp,mid;
	for (int i=1;i<=m;i++){
		cin>>temp;
		ar[temp+d]++;
		days[temp+d].push_back(i);
	}
	l=1;
	r=m;
	while (l<=r){
		mid=(l+r)/2;
		if (check(mid)){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
	out(l);
	return 0;
}

bool check(int mac){
	for(int i = 1; i <= n; i++) {
        tempar[i] = ar[i];
    }
	int macleft;
	int cur=1;
	for (int i=1;i<=n;i++){
		macleft=mac;
		while (macleft>0 && cur<=n){
			if (tempar[cur]>0){
				tempar[cur]--;
				macleft--;
			}
			else{
				cur++;
			}
		}
		if (tempar[i]!=0){
			return 0;
		}
	}
	return 1;
}

void out(int ans){
	int macleft;
	int cur=1;
	int temp;
	for (int i=1;i<=n;i++){
		macleft=ans;
		while (macleft>0 && cur<=n){
			if (ar[cur]>0){
				temp=days[cur][days[cur].size()-1];
				days[cur].pop_back();
				cout<<temp<<" ";
				ar[cur]--;
				macleft--;
			}
			else{
				cur++;
			}
		}
		cout<<0<<endl;
	}
}

• Subtask 1: 55 / 100