제출 #477801

#제출 시각아이디문제언어결과실행 시간메모리
477801erequeJob Scheduling (CEOI12_jobs)C++17
55 / 100
275 ms13860 KiB
/*
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 = -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;
	for(int day = 1; day <= N; day++) {
		if(curr_job >= M) {
			cout << 0 << endl;
			continue;
		}
		for(int j = 0; j < machines; j++) {
			curr_job++;
			if(curr_job >= M) continue;
			cout << jobs[curr_job].sc << " ";
		}
		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;
	// }
}
#Verdict Execution timeMemoryGrader output
Fetching results...