Submission #1280614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280614		yintercept	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	292 ms	16492 KiB

jobs

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

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

int main(){
	cin>>n>>d>>m;
	ll l,r,temp,mid;
	for (ll 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(ll mac){
	for(ll i = 1; i <= n; i++) {
        tempar[i] = ar[i];
    }
	ll macleft;
	ll cur=1;
	for (ll 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(ll ans){
	ll macleft;
	ll cur=1;
	ll temp;
	for (ll 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