Submission #468041

#	Time	Username	Problem	Language	Result	Execution time	Memory
468041		clams	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	512 ms	26388 KiB

jobs

/*
 * Author: bubu2006
**/

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

int n, d, m;
vector<pair<int, int>> req;
    
pair<bool, vector<vector<int>>> ok(int x) {
	vector<vector<int>> res(n);
	int aint = 0;
	for(int day = 1; day <= n; day++) {
		for(int j = 0; j < x; j++) {
			if(req[aint].first > day) {
				break;
			}
			
			if(req[aint].first + d >= day) {
				res[day - 1].push_back(req[aint++].second);
			} else {
				return {0, res};
			}
			
			if(aint == 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(int i = 0; i < m; i++) {
		cin >> req[i].first;
		req[i].second = i + 1;
	}
	
	sort(req.begin(), req.end());
	
	vector<vector<int>> ans;
	
	int l = 0;
	int r = m;
	
	while(l < r - 1) {
		int mid = l + (r - l) / 2;
		auto tmp = ok(mid);
		if(tmp.first) {
			r = mid;
			ans = tmp.second;
		} else {
			l = mid;
		}
	}
	
	cout << r << '\n';
	for(int i = 0; i < n; i++) {
		for(int j : ans[i]) {
			cout << j << ' ';
		}
		cout << 0 << '\n';
	}
}

• Subtask 1: 100 / 100