Submission #1083816

# Submission time Handle Problem Language Result Execution time Memory
1083816 2024-09-04T08:03:49 Z NEMO_ Job Scheduling (CEOI12_jobs) C++17
Compilation error
0 ms 0 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;
y
	for (int day = 1; day <= N; day++) {
		for (int j = 0; j < machineCount; j++) {
			// if all jobs before and on this day are finished,
			// we can go to the next day, even if there are usable machines left
			// we can determine that since the vector jobs is sorted
			if (jobs[reqNum].first > day) break;
			// if the current date is before the deadline for the job
			// we can add this job to the schedule and move to the next job
			// request
			if (jobs[reqNum].first + D >= day)
				schedule[day - 1].push_back(jobs[reqNum++].second);
			// otherwise, it is not feasible due to deadline
			else return mp(false, schedule);

			// if we have processed all the requests, we have found a feasible
			// sol
			if (reqNum == M) return mp(true, schedule);
		}
	}
	// if not all the requests can be processed within the given N days,
	// then it is not feasible
	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;
	// binary search on the number of machines for the minimum possible solution
	// left and right bound, l and r
	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";
	}
}

Compilation message

jobs.cpp: In function 'std::pair<bool, std::vector<std::vector<int> > > isFeasible(const std::vector<std::pair<int, int> >&, int)':
jobs.cpp:16:1: error: 'y' was not declared in this scope
   16 | y
      | ^
jobs.cpp:17:20: error: 'day' was not declared in this scope
   17 |  for (int day = 1; day <= N; day++) {
      |                    ^~~
jobs.cpp:15:6: warning: unused variable 'reqNum' [-Wunused-variable]
   15 |  int reqNum = 0;
      |      ^~~~~~