제출 #1011892

#제출 시각아이디문제언어결과실행 시간메모리
1011892belgianbotJob Scheduling (CEOI12_jobs)C++14
100 / 100
169 ms22040 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> tasks;
int N, D, M;
vector<vector<int>> possible (int nbMachine) {
	queue <pair<int,int>> q;
	vector<vector<int>> ans(N);
	for (int i(0); i < N; i++) {
		if (!q.empty() && i - q.front().second > D) return {};
		int sum = nbMachine;
		for (int x : tasks[i]) q.push({x, i});
		while (!q.empty() && sum > 0) {
			sum--;
			ans[i].push_back(q.front().first);
			q.pop();
		}
	}
	if (!q.empty()) return {};
	return ans;
}
		
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> N >> D >> M;
	tasks.resize(N);
	
	for (int i = 0; i < M; i++) {
		int a; cin >> a; a--;
		tasks[a].push_back(i + 1);
	}
	
	int l = 0, r = 1000000;
	while (l < r) {
		int mid = r - (r - l) / 2;
		//cout << l << " " << r << '\n';
		
		if (possible(mid).empty()) l = mid;
		else r = mid - 1;
	}
	
	cout << l + 1 << '\n';
	vector<vector<int>> ans = possible(l + 1);
	for (auto x : ans) {
		for (int y : x) {
			cout << y  << " ";
		}
		cout << "0\n";
	}
	
	return 0;
}
		
		
#Verdict Execution timeMemoryGrader output
Fetching results...