제출 #525921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525921		pawned	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	644 ms	41664 KiB

jobs

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

int N, D, M;	// days, max delay, reqs
ii numbers[1000050];
vector<int> answers[1000050];

bool check(int n) {	// checks if n machines is enough
	for (int i = 0; i <= N; i++) {
		answers[i].clear();
	}
	int needed[N] = {0};
	for (int i = 0; i < M; i++) {	// finds earliest possible time for each
		int day = numbers[i].fi;
		while (needed[day] == n)
			day++;
		if (day - numbers[i].fi > D)
			return false;
		needed[day]++;
		answers[day].pb(numbers[i].se);
	}
	return true;
}

int main() {
	cin>>N>>D>>M;
	for (int i = 0; i < M; i++) {
		cin>>numbers[i].fi;
		numbers[i].se = i + 1;
	}
	sort(numbers, numbers + M);
	int low = 0;
	int high = 1e9;
	int ans = -1;
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		if (check(mid)) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	cout<<ans<<endl;
	check(ans);
	for (int i = 1; i <= N; i++) {
		for (int j : answers[i])
			cout<<j<<" ";
		cout<<0<<endl;
	}
}

• Subtask 1: 60 / 100