Submission #692515

#	Time	Username	Problem	Language	Result	Execution time	Memory
692515		Snowmanonahoe	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	160 ms	17688 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
struct day {
	vector<int> reqs;
	int due = 0;
};
vector<day> days;
int N;
bool check(int num) {
	int jobs = 0, done = 0;
	for (int i = 1; i <= N; i++) {
		jobs = max(0, jobs + static_cast<int>(days[i].reqs.size()) - num);
		done += num - days[i].due;
		if (done < 0)
			return false;
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int D, M;
	cin >> N >> D >> M;
	days.resize(N+1);
	for (int i = 1; i <= M; i++) {
		int req;
		cin >> req;
		days[req].reqs.push_back(i);
		days[req + D].due++;	
	}
	int l = 1, r = 1e+6;
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	cout << l << '\n';
	queue<int> jobs;
	for (int i = 1; i <= N; i++) {
		for (const auto& i : days[i].reqs)
			jobs.push(i);
		for (int i = 0; i < l && !jobs.empty(); i++) {
			cout << jobs.front() << ' ';
			jobs.pop();
		}
		cout << "0\n";
	}
}

• Subtask 1: 15 / 100