Submission #477803

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477803	2021-10-03T23:16:53 Z	ereque	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	277 ms	13860 KB

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) break;
			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) break;
			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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1864 KB	Output is correct
2	Correct	20 ms	1772 KB	Output is correct
3	Correct	22 ms	1804 KB	Output is correct
4	Correct	27 ms	1744 KB	Output is correct
5	Correct	25 ms	1728 KB	Output is correct
6	Correct	21 ms	1864 KB	Output is correct
7	Correct	23 ms	1800 KB	Output is correct
8	Correct	21 ms	1852 KB	Output is correct
9	Correct	40 ms	2096 KB	Output is correct
10	Correct	38 ms	1980 KB	Output is correct
11	Correct	28 ms	1724 KB	Output is correct
12	Correct	68 ms	3312 KB	Output is correct
13	Correct	92 ms	4708 KB	Output is correct
14	Correct	143 ms	6196 KB	Output is correct
15	Correct	151 ms	7668 KB	Output is correct
16	Correct	186 ms	9164 KB	Output is correct
17	Correct	223 ms	10680 KB	Output is correct
18	Correct	245 ms	12204 KB	Output is correct
19	Correct	277 ms	13860 KB	Output is correct
20	Correct	214 ms	10652 KB	Output is correct