Submission #640064

#	Time	Username	Problem	Language	Result	Execution time	Memory
640064		Trisanu_Das	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	399 ms	13724 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
const int M = 1000005;
#define ff first
#define ss second
 
int n, d, m;
pair <int,int> tasks[M];
 
bool check(int mid){
	int pos = 1;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= mid && pos <= m && tasks[pos].ff <= i; ++j) if(i - tasks[pos++].ff > d) return false;
	return (pos == m + 1);
}
 
int main(){
	cin >> n >> d >> m;
	for(int i = 1; i <= m; ++i) cin >> tasks[i].ff, tasks[i].ss = i;
	sort(tasks + 1, tasks + m + 1);
	int l = 1, r = m + 1;
	while(l < r){
		int mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r << '\n';
	int pos = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= r && pos <= m && tasks[pos].ff <= i; ++j, ++pos) cout << tasks[pos].ss << ' ';
		cout << 0 << '\n';
	}
}

• Subtask 1: 100 / 100