Submission #746189

#	Time	Username	Problem	Language	Result	Execution time	Memory
746189		JellyTheOctopus	Job Scheduling (CEOI12_jobs)	C++17	10 / 100	1086 ms	65536 KiB

jobs

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

int N, D, M;
vector<int> arr[10001];

bool check(int x) {
	queue<int> q;
	int wait = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < (int)arr[i].size(); j++) {
			q.push(i);
		}
		if (!q.empty()) {
			wait = max(wait, i-q.front());
		}
		for (int j = 0; j < x && !q.empty(); j++) {
			q.pop();
		}
	}
	return wait <= D;
}

int main() {
	cin >> N >> D >> M;
	for (int i = 1; i <= M; i++) {
		int t;
		cin >> t;
		arr[t].push_back(i);
	}
	int high = N;
	int low = 0;
	while (low < high) {
		int mid = (high+low)/2;
		if (check(mid)) {
			high = mid-1;
		}
		else {
			low = mid;
		}
	}
	int ans = high+1;
	cout << ans << "\n";
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		for (auto v: arr[i]) {
			q.push(v);
		}
		for (int j = 0; j < ans && !q.empty(); j++) {
			cout << q.front() << ' ';
			q.pop();
		}
		cout << 0 << '\n';
	}	
}

• Subtask 1: 10 / 100