Submission #1015821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015821		ssitaram	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	356 ms	26072 KiB

jobs

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int n, d, m; cin >> n >> d >> m;
	vector<pair<int, int>> jobs(m);
	for (int i = 0; i < m; ++i) {
		cin >> jobs[i].first;
		--jobs[i].first;
		jobs[i].second = i + 1;
	}
	sort(jobs.begin(), jobs.end());
	auto plan = [&](int mach) -> pair<bool, vector<vector<int>>> {
		vector<vector<int>> pl(n);
		int idx = 0;
		bool works = 1;
		for (int i = 0; i < m; ++i) {
			if (idx == n) {
				works = 0;
				break;
			}
			while (idx < jobs[i].first) {
				++idx;
			}
			pl[idx].push_back(jobs[i].second);
			if (idx > jobs[i].first + d) {
				works = 0;
				break;
			}
			if (pl[idx].size() == mach) {
				++idx;
			}
		}
		return make_pair(works, pl);
	};
	int lo = 1, hi = m;
	while (lo < hi) {
		int mi = (lo + hi) / 2;
		if (plan(mi).first) {
			hi = mi;
		} else {
			lo = mi + 1;
		}
	}
	cout << lo << '\n';
	vector<vector<int>> pl = plan(lo).second;
	for (vector<int>& day : pl) {
		for (int v : day) {
			cout << v << ' ';
		}
		cout << "0\n";
	}
	return 0;
}

Compilation message (stderr)

jobs.cpp: In lambda function:
jobs.cpp:32:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |    if (pl[idx].size() == mach) {
      |        ~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 100 / 100