Submission #477800

#	Time	Username	Problem	Language	Result	Execution time	Memory
477800		ereque	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	276 ms	23592 KiB

jobs

#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;
vector<vector<int> > poss;

bool test(int machines) {

	int curr_job = -1;
	for(int day = 1; day <= N && curr_job < M; day++) {
		for(int j = 0; j < machines; j++) {
			curr_job++;
			if(curr_job >= M) return true;

			int delay = day-jobs[curr_job].fs;
			if(delay > D) {
				return false;
			}
		}
	}
	return true;
}

void find_poss(int machines) {

	int curr_job = -1;
	poss.resize(N+1);
	for(int day = 1; day <= N && curr_job < M; day++) {
		for(int j = 0; j < machines; j++) {
			curr_job++;
			if(curr_job >= M) return;
			poss[day].pb(jobs[curr_job].sc);
			// cout << day << ": " << jobs[curr_job].sc << 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;
		}
	}

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