Submission #670339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670339	2022-12-08T17:16:01 Z	Charizard2021	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	510 ms	29848 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	3304 KB	Output is correct
2	Correct	40 ms	3232 KB	Output is correct
3	Correct	40 ms	3272 KB	Output is correct
4	Correct	40 ms	3264 KB	Output is correct
5	Correct	40 ms	3336 KB	Output is correct
6	Correct	44 ms	3380 KB	Output is correct
7	Correct	41 ms	3240 KB	Output is correct
8	Correct	41 ms	3216 KB	Output is correct
9	Correct	89 ms	9916 KB	Output is correct
10	Correct	89 ms	9920 KB	Output is correct
11	Correct	54 ms	3184 KB	Output is correct
12	Correct	103 ms	5660 KB	Output is correct
13	Correct	147 ms	9676 KB	Output is correct
14	Correct	255 ms	12728 KB	Output is correct
15	Correct	272 ms	12900 KB	Output is correct
16	Correct	370 ms	18888 KB	Output is correct
17	Correct	414 ms	22032 KB	Output is correct
18	Correct	433 ms	26184 KB	Output is correct
19	Correct	510 ms	29848 KB	Output is correct
20	Correct	411 ms	22108 KB	Output is correct