Submission #1015821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015821	2024-07-06T21:25:48 Z	ssitaram	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	356 ms	26072 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	3032 KB	Output is correct
2	Correct	32 ms	2928 KB	Output is correct
3	Correct	30 ms	2940 KB	Output is correct
4	Correct	30 ms	2944 KB	Output is correct
5	Correct	30 ms	2948 KB	Output is correct
6	Correct	32 ms	3168 KB	Output is correct
7	Correct	31 ms	2952 KB	Output is correct
8	Correct	31 ms	2892 KB	Output is correct
9	Correct	56 ms	7568 KB	Output is correct
10	Correct	52 ms	7596 KB	Output is correct
11	Correct	33 ms	2652 KB	Output is correct
12	Correct	62 ms	5036 KB	Output is correct
13	Correct	92 ms	7904 KB	Output is correct
14	Correct	149 ms	11048 KB	Output is correct
15	Correct	172 ms	11608 KB	Output is correct
16	Correct	209 ms	14664 KB	Output is correct
17	Correct	242 ms	19140 KB	Output is correct
18	Correct	291 ms	19716 KB	Output is correct
19	Correct	356 ms	26072 KB	Output is correct
20	Correct	258 ms	19176 KB	Output is correct