oj.uz

답안 #670339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670339 2022-12-08T17:16:01 Z Charizard2021 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 510 ms 29848 KB 
#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

# 결과 실행 시간 메모리 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