oj.uz

Submission #858465

# Submission time Handle Problem Language Result Execution time Memory
858465 2023-10-08T14:04:15 Z ilef Job Scheduling (CEOI12_jobs) C++14
100 / 100
 333 ms 26488 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define mp make_pair
using pi = pair<int, int>;
using vi = vector<int>;
int N, D, M;

pair<bool, vector<vi>> isFeasible(const vector<pi> &jobs, int machineCount) {
	vector<vi> schedule(N);
	int reqNum = 0;
	for (int day = 1; day <= N; day++) {
		for (int j = 0; j < machineCount; j++) {
			if (jobs[reqNum].first > day) break;
			if (jobs[reqNum].first + D >= day)
				schedule[day - 1].push_back(jobs[reqNum++].second);
			else return mp(false, schedule);
			if (reqNum == M) return mp(true, schedule);
		}
	}
	return mp(false, schedule);
}

int main() {
	cin.tie(0)->sync_with_stdio(false);

	cin >> N >> D >> M;
	vector<pi> jobs(M);
	for (int i = 0; i < M; i++) {
		int day;
		cin >> day;
		jobs[i] = mp(day, i + 1);
	}
	sort(all(jobs));

	vector<vi> result;
	int l = 1, r = M;
	while (l < r) {
		int machineNum = (l + r) / 2;
		pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
	
		if (curResult.first) {
			r = machineNum;
			result = curResult.second;
		}
		else
			l = machineNum + 1;
	}

	cout << l << "\n";
	for (int i = 0; i < N; i++) {
		for (int &idx : result[i]) cout << idx << " ";
		cout << 0 << "\n";
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3216 KB Output is correct
2 Correct 23 ms 3220 KB Output is correct
3 Correct 23 ms 3220 KB Output is correct
4 Correct 24 ms 3092 KB Output is correct
5 Correct 23 ms 3092 KB Output is correct
6 Correct 24 ms 3092 KB Output is correct
7 Correct 24 ms 3156 KB Output is correct
8 Correct 23 ms 3088 KB Output is correct
9 Correct 77 ms 9816 KB Output is correct
10 Correct 66 ms 9884 KB Output is correct
11 Correct 29 ms 2872 KB Output is correct
12 Correct 58 ms 5100 KB Output is correct
13 Correct 81 ms 8556 KB Output is correct
14 Correct 138 ms 10932 KB Output is correct
15 Correct 153 ms 11024 KB Output is correct
16 Correct 197 ms 16188 KB Output is correct
17 Correct 235 ms 18788 KB Output is correct
18 Correct 279 ms 23220 KB Output is correct
19 Correct 333 ms 26488 KB Output is correct
20 Correct 232 ms 18968 KB Output is correct