oj.uz

답안 #1104712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104712 2024-10-24T09:12:45 Z Muhammet Job Scheduling (CEOI12_jobs) C++17
100 / 100
 261 ms 13876 KB 
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

int T, n, m, d;

vector <pair<int,int>> a;

bool check(int x){
	int ind = -1, day = 0;
	while(ind < m-1){
		day++;
		for(int i = ind+1; i <= min(ind+x,m-1); i++){
			if(day < a[i].ff){
				ind = i-1;
				ind -= x;
				break;
			}
			if(a[i].ff + d < day){
				return false;
			}
		}
		ind += x;
	}
	if(day > n) return false;
	return true;
}

int main(){
	cin >> n >> d >> m;
	a.resize(m);
	for(int i = 0; i < m; i++){
		cin >> a[i].ff;
		a[i].ss = i+1;
	}
	sort(a.begin(), a.end());
	int l = 1, r = m, k = m;
	while(l <= r){
		int md = (l + r) / 2;
		if(check(md)){
			r = md-1;
			k = md;
		}
		else {
			l = md+1;
		}
	}
	cout << k << '\n';
	int ind = -1, cnt = 0;
	while(ind < m-1){
		cnt++;
		for(int i = ind+1; i <= min(ind+k,m-1); i++){
			if(cnt < a[i].ff){
				ind = i-1;
				ind -= k;
				break;
			}
			cout << a[i].ss << " ";
		}
		ind += k;
		cout << "0\n";
	}
	for(int i = cnt+1; i <= n; i++){
		cout << "0\n";
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1616 KB Output is correct
2 Correct 20 ms 1748 KB Output is correct
3 Correct 20 ms 1616 KB Output is correct
4 Correct 20 ms 1616 KB Output is correct
5 Correct 20 ms 1608 KB Output is correct
6 Correct 20 ms 1616 KB Output is correct
7 Correct 20 ms 1752 KB Output is correct
8 Correct 20 ms 1616 KB Output is correct
9 Correct 27 ms 1948 KB Output is correct
10 Correct 27 ms 1872 KB Output is correct
11 Correct 27 ms 1616 KB Output is correct
12 Correct 54 ms 3148 KB Output is correct
13 Correct 81 ms 4568 KB Output is correct
14 Correct 116 ms 6124 KB Output is correct
15 Correct 157 ms 7668 KB Output is correct
16 Correct 195 ms 9216 KB Output is correct
17 Correct 205 ms 10576 KB Output is correct
18 Correct 238 ms 12104 KB Output is correct
19 Correct 261 ms 13876 KB Output is correct
20 Correct 234 ms 10568 KB Output is correct