Submission #468037

#	Time	Username	Problem	Language	Result	Execution time	Memory
468037		clams	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	560 ms	45400 KiB

jobs

/*
 * Author: bubu2006
**/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


ll n, d, m;
vector<pair<ll, ll>> req;
    
pair<bool, vector<vector<ll>>> ok(ll x) {
	vector<vector<ll>> res(n);
	ll all = 0;
	for(ll day = 1; day <= n; day++) {
		for(ll j = 0; j < x; j++) {
			if(req[all].first > day) {
				break;
			}
			
			if(req[all].first + d >= day) {
				res[day - 1].push_back(req[all++].second);
			} else {
				return {0, res};
			}
			
			if(all == m) {
				return {1, res};
			}
		}
	}
	
	return {0, res};
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
	cin >> n >> d >> m;
	
	req.resize(m);
	for(ll i = 0; i < m; i++) {
		cin >> req[i].first;
		req[i].second = i + 1;
	}
	
	sort(req.begin(), req.end());
	
	vector<vector<ll>> ans;
	
	ll l = 0;
	ll r = m + 1;
	
	while(l < r - 1) {
		ll mid = l + (r - l) / 2;
		
		auto tmp = ok(mid);
		if(tmp.first == true) {
			r = mid;
			ans = tmp.second;
		} else {
			l = mid;
		}
	}
	
	cout << l << '\n';
	for(int i = 0; i < n; i++) {
		for(auto j : ans[i]) {
			cout << j << ' ';
		}
		cout << 0 << '\n';
	}
}

• Subtask 1: 0 / 100