Submission #476456

#	Time	Username	Problem	Language	Result	Execution time	Memory
476456		qwerty1234	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	659 ms	31708 KiB

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 / 100