Submission #1011892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011892		belgianbot	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	169 ms	22040 KiB

jobs

#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;
}
		
		

• Subtask 1: 100 / 100