Submission #1104712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104712		Muhammet	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	261 ms	13876 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

int T, n, m, d;

vector <pair<int,int>> a;

bool check(int x){
	int ind = -1, day = 0;
	while(ind < m-1){
		day++;
		for(int i = ind+1; i <= min(ind+x,m-1); i++){
			if(day < a[i].ff){
				ind = i-1;
				ind -= x;
				break;
			}
			if(a[i].ff + d < day){
				return false;
			}
		}
		ind += x;
	}
	if(day > n) return false;
	return true;
}

int main(){
	cin >> n >> d >> m;
	a.resize(m);
	for(int i = 0; i < m; i++){
		cin >> a[i].ff;
		a[i].ss = i+1;
	}
	sort(a.begin(), a.end());
	int l = 1, r = m, k = m;
	while(l <= r){
		int md = (l + r) / 2;
		if(check(md)){
			r = md-1;
			k = md;
		}
		else {
			l = md+1;
		}
	}
	cout << k << '\n';
	int ind = -1, cnt = 0;
	while(ind < m-1){
		cnt++;
		for(int i = ind+1; i <= min(ind+k,m-1); i++){
			if(cnt < a[i].ff){
				ind = i-1;
				ind -= k;
				break;
			}
			cout << a[i].ss << " ";
		}
		ind += k;
		cout << "0\n";
	}
	for(int i = cnt+1; i <= n; i++){
		cout << "0\n";
	}
	return 0;
}

• Subtask 1: 100 / 100