Submission #1015819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015819	2024-07-06T21:19:43 Z	ssitaram	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	326 ms	26140 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 = n;
	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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	12 ms	1928 KB	Output isn't correct
2	Incorrect	12 ms	2036 KB	Output isn't correct
3	Incorrect	12 ms	1900 KB	Output isn't correct
4	Incorrect	12 ms	1932 KB	Output isn't correct
5	Incorrect	11 ms	1908 KB	Output isn't correct
6	Incorrect	11 ms	1900 KB	Output isn't correct
7	Incorrect	11 ms	1932 KB	Output isn't correct
8	Incorrect	10 ms	1896 KB	Output isn't correct
9	Correct	67 ms	7472 KB	Output is correct
10	Correct	63 ms	7576 KB	Output is correct
11	Correct	23 ms	2644 KB	Output is correct
12	Correct	49 ms	5104 KB	Output is correct
13	Correct	76 ms	7984 KB	Output is correct
14	Correct	111 ms	11024 KB	Output is correct
15	Correct	128 ms	11692 KB	Output is correct
16	Correct	178 ms	14888 KB	Output is correct
17	Correct	217 ms	19092 KB	Output is correct
18	Correct	260 ms	19708 KB	Output is correct
19	Correct	326 ms	26140 KB	Output is correct
20	Correct	229 ms	19088 KB	Output is correct