oj.uz

답안 #713911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713911 2023-03-23T08:12:28 Z iskhakkutbilim Job Scheduling (CEOI12_jobs) C++14
100 / 100
 252 ms 13808 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()


main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   int n, m, k;
	cin >> n >> m >> k;
	vector<pair<int, int> > job(k);
	for(int i = 0;i < k; i++){
		cin >> job[i].ff;
		job[i].ss = i;
	}
	sort(all(job));
	function<int(int, int)> good=[&](int machine, int pr){
		int j = 0;
		for(int i = 1;i <= n; i++){
			int cnt = 0;
			while(cnt < machine && j < k){
				if(i < job[j].ff) break;
				if(i > job[j].ff + m) return 0;
				if(pr) cout << job[j].ss+1 << ' ';
				j++, cnt++;
			}
			if(pr) cout << 0 << '\n';	
		}
		if(j < k) return 0;
		return 1;
	};
	/*
	8 2 12
	1 2 4 2 1 3 5 6 2 3 6 4
	*/
	int l = 0, r = (int)2e6;
	while(l + 1 < r){
		int mid = (l + r)>>1;
		if(good(mid, 0)){
			r = mid;
		}else{
			l = mid;
		}
	}
	cout << r << '\n';
	if(!good(r, 0)) assert(false);
	good(r, 1);
	return 0;
}

Compilation message

jobs.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1620 KB Output is correct
2 Correct 19 ms 1748 KB Output is correct
3 Correct 20 ms 1620 KB Output is correct
4 Correct 21 ms 1620 KB Output is correct
5 Correct 26 ms 1620 KB Output is correct
6 Correct 18 ms 1620 KB Output is correct
7 Correct 18 ms 1628 KB Output is correct
8 Correct 18 ms 1732 KB Output is correct
9 Correct 32 ms 1820 KB Output is correct
10 Correct 39 ms 1888 KB Output is correct
11 Correct 24 ms 1620 KB Output is correct
12 Correct 53 ms 3148 KB Output is correct
13 Correct 85 ms 4576 KB Output is correct
14 Correct 121 ms 6124 KB Output is correct
15 Correct 128 ms 7612 KB Output is correct
16 Correct 163 ms 9052 KB Output is correct
17 Correct 195 ms 10536 KB Output is correct
18 Correct 207 ms 12108 KB Output is correct
19 Correct 252 ms 13808 KB Output is correct
20 Correct 199 ms 10576 KB Output is correct