oj.uz

답안 #50312

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
50312 2018-06-10T03:57:03 Z faishol27 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 635 ms 13988 KB 
#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

# 결과 실행 시간 메모리 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