Submission #545596

#	Time	Username	Problem	Language	Result	Execution time	Memory
545596		aidan0626	Job Scheduling (CEOI12_jobs)	C++14	46 / 100	527 ms	29752 KiB

jobs

#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 << endl;
	for (int i=0; i<N; i++) {
		for (int &idx : result[i])
			cout << idx << " ";
		cout << 0 << endl;
	}
}

• Subtask 1: 46 / 100