Submission #476456

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
476456	2021-09-27T05:12:20 Z	qwerty1234	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	659 ms	31708 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int N, D, M;

struct ValidScheduler {
	bool valid;
	vector<vector<int>> scheduler;
};

ValidScheduler check(int mid, vector<vector<int>> &assign) {
	queue<pair<int, int>> delayed;
	vector<vector<int>> schedule(N);
	ValidScheduler ans;
	for (int i = 0; i < N; i++) {
		int numMachines = mid;
		if (!delayed.empty()) {
			int numRemove = min((int)delayed.size(), numMachines);
			for (int j = 0; j < numRemove; j++) {
				pair<int, int> delayedReq = delayed.front();
				if (i - delayedReq.second > D) {
					ans.valid = false;
					return ans;
				}
				schedule[i].push_back(delayedReq.first);
				delayed.pop();
				numMachines--;
			}
		}
		for (int j = 0; j < (int)assign[i].size(); j++) {
			if (j < numMachines) {
				schedule[i].push_back(assign[i][j]);
			}
			else {
				delayed.push({ assign[i][j], i });
			}
		}
	}
	ans.valid = true;
	ans.scheduler = schedule;
	// for (int i = 0; i < N; i++) {
	// 	for (int j = 0; j < (int)schedule[i].size(); j++) {
	// 		cout << schedule[i][j] << ' ';
	// 	}
	// 	cout << 0 << '\n';
	// }
	return ans;
}

int main() {
	cin >> N >> D >> M;
	vector<vector<int>> assign(N);
	for (int i = 0; i < M; i++) {
		int req;
		cin >> req;
		req--;
		assign[req].push_back(i + 1);
	}
	// for (int i = 0; i < N; i++) {
	// 	cout << "Day: " << i << " , ";
	// 	for (int j = 0; j < assign[i].size(); j++) {
	// 		cout << assign[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	vector<vector<int>> schedule(N);
	int ans = 0;
	int l = 1;
	int r = M;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		// cout << l << ' ' << r << ' ' << mid << '\n';
		if (check(mid, assign).valid) {
			schedule = check(mid, assign).scheduler;
			ans = mid;
			r = mid - 1;
			// cout << "NEXT\n";
		} else {
			l = mid + 1;
		}
	}
	cout << ans << '\n';
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < (int)schedule[i].size(); j++) {
			cout << schedule[i][j] << ' ';
		}
		cout << 0 << '\n';
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	3544 KB	Output is correct
2	Correct	48 ms	3652 KB	Output is correct
3	Correct	47 ms	3544 KB	Output is correct
4	Correct	47 ms	3544 KB	Output is correct
5	Correct	48 ms	3572 KB	Output is correct
6	Correct	57 ms	3552 KB	Output is correct
7	Correct	46 ms	3548 KB	Output is correct
8	Correct	44 ms	3540 KB	Output is correct
9	Correct	96 ms	12616 KB	Output is correct
10	Correct	93 ms	12616 KB	Output is correct
11	Correct	64 ms	2792 KB	Output is correct
12	Correct	134 ms	5472 KB	Output is correct
13	Correct	187 ms	8832 KB	Output is correct
14	Correct	376 ms	12604 KB	Output is correct
15	Correct	327 ms	12556 KB	Output is correct
16	Correct	603 ms	17192 KB	Output is correct
17	Correct	625 ms	21740 KB	Output is correct
18	Correct	543 ms	21524 KB	Output is correct
19	Correct	659 ms	31708 KB	Output is correct
20	Correct	621 ms	21720 KB	Output is correct