Submission #477802

#	Time	Username	Problem	Language	Result	Execution time	Memory
477802		ereque	Job Scheduling (CEOI12_jobs)	C++14	65 / 100	1099 ms	13116 KiB

jobs

/*
ID: erickca2
TASK: cowdance
LANG: C++                 
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// #define int long long
#define endl '\n'
#define pb push_back
#define fs first
#define sc second
#define pii pair<int, int>

const int MAXN = 2*1e5+8;

int N, D, M;
vector<pii> jobs;

bool test(int machines) {

	int curr_job = 0;
	for(int day = 1; day <= N && curr_job < M; day++) {
		for(int j = 0; j < machines; j++) {
			if(curr_job >= M) return true;
			int delay = day-jobs[curr_job].fs;
			if(delay < 0) continue;
			if(delay > D) {
				return false;
			}
			curr_job++;

		}
	}
	return true;
}

void find_poss(int machines) {

	int curr_job = 0;
	for(int day = 1; day <= N; day++) {
		if(curr_job >= M) {
			cout << 0 << endl;
			continue;
		}
		for(int j = 0; j < machines; j++) {
			if(curr_job >= M) continue;
			int delay = day-jobs[curr_job].fs;
			// cout << "seeing job " << jobs[]
			if(delay < 0) continue;
			cout << jobs[curr_job].sc << " ";
			curr_job++;

		}
		cout << 0 << endl;
	}
	return;

}

int32_t main() {
	ios_base::sync_with_stdio(NULL); cin.tie(0);
	cin >> N >> D >> M;

	for(int i = 1; i <= M; i++) {
		int x;
		cin >> x;
		pii j = {x, i};
		jobs.pb(j);
	}

	sort(jobs.begin(), jobs.end());

	int l = 1, r = 1e6+8;
	int ans = -1;

	while(l <= r) {
		int mid = l+(r-l)/2;
		if(test(mid)) {
			ans = mid;
			r = mid-1;
		} else {
			l = mid+1;
		}
	}

	cout << ans << endl;
	find_poss(ans);

	// cout << ans << endl;
	// for(int i = 1; i <= N; i++) {
		// for(auto x : poss[i]) {
			// cout << x << " ";
		// }
		// cout << 0 << endl;
	// }
}

• Subtask 1: 65 / 100