oj.uz

답안 #556132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556132 2022-05-02T12:48:52 Z dhruv_kalmekh Job Scheduling (CEOI12_jobs) C++17
100 / 100
 579 ms 29704 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m,d;
vector<pair<int,int>> vec;


pair<bool,vector<vector<int>>> f(int x){
	vector<vector<int>> schedule(n);
	int req=0;
	for(int day=1;day<=n;day++){
		for(int i=0;i<x;i++){
			if(vec[req].first>day){
				break;
			}
			if(vec[req].first+d >= day){
				schedule[day-1].push_back(vec[req++].second);
			}
			else{
				return make_pair(false,schedule);
			}
			if(req==m){
				return make_pair(true,schedule);
			}
		}
	}
	return make_pair(false,schedule);
}

int main(){
	cin >> n >> d >> m;
	vec.resize(m);
	for(int i=0;i<m;i++){
		int day;
		cin >> day;
		vec[i] = make_pair(day,i+1);
	}
	sort(vec.begin(),vec.end());
	vector<vector<int>> result;
	int l=0,r=m;
	while(l<r){
		int mid = l + (r-l)/2;
		pair<bool,vector<vector<int>>> cur = f(mid);
		if(cur.first){
			r = mid; 
			result = cur.second;
		}
		else{
			l = mid+1;
		}
	}
	cout << l << "\n";
	for(int i=0;i<n;i++){
		for(int j : result[i]){
			cout << j << " ";
		}
		cout << 0 << "\n";
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 3216 KB Output is correct
2 Correct 43 ms 3264 KB Output is correct
3 Correct 42 ms 3240 KB Output is correct
4 Correct 41 ms 3232 KB Output is correct
5 Correct 41 ms 3224 KB Output is correct
6 Correct 41 ms 3332 KB Output is correct
7 Correct 42 ms 3256 KB Output is correct
8 Correct 45 ms 3336 KB Output is correct
9 Correct 114 ms 9936 KB Output is correct
10 Correct 93 ms 9980 KB Output is correct
11 Correct 53 ms 3096 KB Output is correct
12 Correct 107 ms 5740 KB Output is correct
13 Correct 148 ms 9664 KB Output is correct
14 Correct 257 ms 12732 KB Output is correct
15 Correct 317 ms 12772 KB Output is correct
16 Correct 399 ms 18664 KB Output is correct
17 Correct 495 ms 22128 KB Output is correct
18 Correct 494 ms 21568 KB Output is correct
19 Correct 579 ms 29704 KB Output is correct
20 Correct 452 ms 22196 KB Output is correct