Submission #1007184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007184		DON_F	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	173 ms	17236 KiB

jobs

#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){
				if (day > a[j].first + d){
					return false;
				}
				++j;
				++k;
			}
		}
		return true;
	};
	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 = 0; i < n; ++i){
		int k = 0;
		while (k < ans && j < m){
			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
	*/
} 

• Subtask 1: 55 / 100