제출 #556132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556132		dhruv_kalmekh	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	579 ms	29704 KiB

jobs

#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 / 100