oj.uz

답안 #744290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744290 2023-05-18T10:32:53 Z MODDI Job Scheduling (CEOI12_jobs) C++14
100 / 100
 482 ms 13884 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, d, m;
vector<pii> arr;
bool check(int machines){
	ll day = 1 , cnt = 0 ;
    for(int i=0;i<m;i++){
        if(day < arr[i].first){
            day = arr[i].first ;
            cnt = 0 ;
        }
        if(day <= arr[i].first + d){ // do job i-th
            cnt++ ;
        }
        else {
            return false ;
        }
        if(cnt == machines){
            day++;
            cnt = 0 ;
        }
    }
 
    if(cnt == 0) day--;
 
    return day <= n ;
}
int main(){
	cin>>n>>d>>m;
	arr.resize(m);
	for(int i = 0; i < m; i++)
	{
		cin>>arr[i].first;
		arr[i].second = i+1;
	}
	sort(arr.begin(), arr.end());
	int l = 1, r = m, ans = 0;
	while(l <= r){
		int mid = (l + r) / 2;
		bool can = check(mid);
		if(can){
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
//	cout<<ans<<endl;
	cout<<ans<<endl;
	for(int i = 1, j = 0; i <= n; i++){
		for(int k = 0; j < m && k < ans; j++, k++)
			cout<<arr[j].second<<" ";
		cout<<0<<endl;
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 1620 KB Output is correct
2 Correct 41 ms 1688 KB Output is correct
3 Correct 41 ms 1680 KB Output is correct
4 Correct 43 ms 1612 KB Output is correct
5 Correct 45 ms 1616 KB Output is correct
6 Correct 41 ms 1628 KB Output is correct
7 Correct 48 ms 1596 KB Output is correct
8 Correct 42 ms 1620 KB Output is correct
9 Correct 156 ms 1852 KB Output is correct
10 Correct 153 ms 1828 KB Output is correct
11 Correct 46 ms 1584 KB Output is correct
12 Correct 85 ms 3152 KB Output is correct
13 Correct 122 ms 4568 KB Output is correct
14 Correct 186 ms 6092 KB Output is correct
15 Correct 201 ms 7544 KB Output is correct
16 Correct 261 ms 9084 KB Output is correct
17 Correct 317 ms 10508 KB Output is correct
18 Correct 338 ms 12040 KB Output is correct
19 Correct 482 ms 13884 KB Output is correct
20 Correct 318 ms 10568 KB Output is correct