Submission #1007314

#TimeUsernameProblemLanguageResultExecution timeMemory
1007314DON_FJob Scheduling (CEOI12_jobs)C++14
100 / 100
165 ms17096 KiB
#include <bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; ++i){
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a.begin(), a.end());
	auto Work = [&](int num){
		int j = 0;
		for (int day = 1; day <= n; ++day){
		    int k = 0;
		    while (j < m && k < num && day >= a[j].first){
				if (day > a[j].first + d){
					return false;
				}
				++j;
				++k;
			}
		}
		return (j == m);
	};
	int lo = 1, hi = m, ans = -1;
	while (lo <= hi){
		int mid = lo + (hi - lo) / 2;
		if (Work(mid)){
			ans = mid;
			hi = mid - 1;
		}else{
			lo = mid + 1;
		}
	}
    cout << ans << "\n";
    int j = 0;
    for (int i = 1; i <= n; ++i){
		int k = 0;
	    while (j < m && k < ans && i >= a[j].first){
			cout << a[j].second + 1 << " ";
			++j;
			++k;
		}
		cout << "0\n";
	}
	/*
	8 2 12
	1 2 4 2 1 3 5 6 2 3 6 4
	*/
} 
#Verdict Execution timeMemoryGrader output
Fetching results...