Submission #744287

#TimeUsernameProblemLanguageResultExecution timeMemory
744287MODDIJob Scheduling (CEOI12_jobs)C++14
10 / 100
516 ms23900 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, d, m;
vector<pii> arr;
bool check(int machines){
	int job = m-1;
	for(int day = n; day >= 1; day--){
		int cnt = 0;
		while(arr[job].first - day <= d && cnt + 1 <= machines){
			job--;
			cnt++;
		}
		if(job < 0)	return true;
	}
	return false;
}
int main(){
	cin>>n>>d>>m;
	arr.resize(m);
	for(int i = 0; i < m; i++)
	{
		cin>>arr[i].first;
		arr[i].second = i+1;
	}
	sort(arr.begin(), arr.end());
	int l = 1, r = 1e6+10, ans = -1;
	while(l <= r){
		int mid = (l + r) / 2;
		bool can = check(mid);
		if(can){
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
//	cout<<ans<<endl;
	vi each_day[n+1];
	int job = m-1;
	for(int day = n; day >= 1; day--){
		int cnt = 0;
		while(job >= 0 && arr[job].first - day <= d && cnt + 1 <= ans){
			each_day[day].pb(arr[job].second);
			job--;
			cnt++;
		}
	}
	cout<<ans<<endl;
	for(int day = 1; day <= n; day++){
		for(auto t : each_day[day])
			cout<<t<<" ";
		cout<<0<<endl;
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...