Submission #670339

#	Time	Username	Problem	Language	Result	Execution time	Memory
670339		Charizard2021	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	510 ms	29848 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
int n, d, m;
pair<bool, vector<vector<int> > > works(const vector<pair<int, int> > &jobs, int machineCount){
	vector<vector<int> > schedule(n);
	int reqNum = 0;
	for (int day = 1; day <= n; day++){
		for (int j = 0; j < machineCount; j++){
			if (jobs[reqNum].first > day){
				break;
			}
			if (jobs[reqNum].first + d >= day){
				schedule[day - 1].push_back(jobs[reqNum++].second);
			}
			else{
				return make_pair(false, schedule);
			}
			if (reqNum == m){
				return make_pair(true, schedule);
			}
		}
	}
	return make_pair(false, schedule);
}
int main(){
    cin >> n >> d >> m;
	vector<pair<int, int> > jobs(m);
	for (int i = 0; i < m; i++){
		int day;
		cin >> day;
		jobs[i] = make_pair(day, i + 1);
	}
	sort(jobs.begin(), jobs.end());
	vector<vector<int> > result;
	int l = 1, r = m;
	while (l < r){
		int machineNum = (l + r) / 2;
		pair<bool, vector<vector<int> > > curResult = works(jobs, machineNum);
		if (curResult.first){
			r = machineNum;
			result = curResult.second;
		}
		else{
			l = machineNum + 1;
		}
	}
	cout << l << "\n";
	for(int i = 0; i < n; i++){
	    for(int &idx : result[i]){
	        cout << idx << " ";
	    }
	    cout << 0 << "\n";
	}
}

• Subtask 1: 100 / 100