Submission #50312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50312	2018-06-10T03:57:03 Z	faishol27	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	635 ms	13988 KB

jobs

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

const int MAXN = 1e5+5;
const int MAXM = 1e6+5;

struct job{
	int ind, day;
};

int N, D, M, mesin_ans = MAXM;
job data[MAXM];

bool isJobCompleted(int mesin){
	int pos = 0;

	for(int i=1;i<=N;i++){
		for(int j=0;j < mesin && data[pos].day <= i && pos < M;j++){
			if(i > data[pos].day+D) return 0; 
			pos++;
		}
	}

	return 1;
}

void print_ans(){
	int pos = 0;

	cout << mesin_ans << endl;
	for(int i=1;i<=N;i++){
		for(int j=0;j < mesin_ans && data[pos].day <= i && pos < M;j++){
			cout << data[pos].ind << " ";
			pos++;
		}

		cout << 0 << endl;
	}
}

bool cmp(job a, job b){
	if(a.day == b.day) return a.ind < b.ind;
	return a.day < b.day;
}

int main(){

	cin >> N >> D >> M;
	for(int i=0;i<M;i++){
		cin >> data[i].day;
		data[i].ind = i+1;
	}
	
	sort(data, data+M, cmp);

	int l = 1,
		r = M;
	while(l<=r){
		int mid = (l+r)/2;
		
		if(isJobCompleted(mid)){
			mesin_ans = min(mid, mesin_ans);
			r = mid-1;
		}else l = mid+1;	
	}

	print_ans();

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	1784 KB	Output is correct
2	Correct	59 ms	1916 KB	Output is correct
3	Correct	61 ms	1916 KB	Output is correct
4	Correct	63 ms	1916 KB	Output is correct
5	Correct	64 ms	2128 KB	Output is correct
6	Correct	60 ms	2128 KB	Output is correct
7	Correct	63 ms	2128 KB	Output is correct
8	Correct	58 ms	2128 KB	Output is correct
9	Correct	188 ms	2272 KB	Output is correct
10	Correct	193 ms	2272 KB	Output is correct
11	Correct	56 ms	2272 KB	Output is correct
12	Correct	108 ms	3320 KB	Output is correct
13	Correct	157 ms	4968 KB	Output is correct
14	Correct	242 ms	6496 KB	Output is correct
15	Correct	270 ms	7852 KB	Output is correct
16	Correct	358 ms	9516 KB	Output is correct
17	Correct	416 ms	10792 KB	Output is correct
18	Correct	460 ms	12376 KB	Output is correct
19	Correct	635 ms	13988 KB	Output is correct
20	Correct	431 ms	13988 KB	Output is correct