답안 #858473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858473 2023-10-08T14:12:30 Z ilef Job Scheduling (CEOI12_jobs) C++14
100 / 100
225 ms 13692 KB
#include <bits/stdc++.h>
using namespace std;
const int M=1e6+12;
int n,d,m;
 pair<int,int>a[M];
bool good(int num) {
     int i=0;
     int day=1;
     int cnt=0;
     while(i<m){
         if(cnt==num){
             cnt=0;
             day++;
         }
         if(a[i].first>day){
             day=a[i].first;
             cnt=0;
         }
         else if(a[i].first+d<day){
             return false;
         }
         i++;
         cnt++;
     }
     return day<=n;
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
	cin>>n>>d>>m;
   
	for(int i=0;i<m;i++){
	    cin>>a[i].first;
	    a[i].second=i;
	}
	sort(a,a+m);
	int l=1;
	int r=m;
	int mid=(l+r)/2;
	while(l<r){
	     mid=(l+r)/2;
	    if(good(mid)){
	        r=mid;
	    }
	    else{
	        l=mid+1;
	    }
	}
	int cnt=0;
	cout<<l<<"\n";
	int days=1;
	for(int i=0;i<m;i++){
	    if(a[i].first<=days){
	     cout<<a[i].second+1<<" ";
	     cnt++;
	      if(cnt==l){
	        cout<<0<<"\n";
	        cnt=0;
	        days++;}}
	         else{
	        cout<<0<<"\n";
	         days++;
	        cnt=0;
	         }
	    
	}
	for(int i=days;i<=n;i++){
	    cout<<0<<"\n";
	}
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3164 KB Output is correct
2 Correct 13 ms 3164 KB Output is correct
3 Correct 16 ms 3164 KB Output is correct
4 Correct 13 ms 3160 KB Output is correct
5 Correct 14 ms 3208 KB Output is correct
6 Correct 13 ms 3164 KB Output is correct
7 Correct 15 ms 3232 KB Output is correct
8 Correct 13 ms 3164 KB Output is correct
9 Correct 24 ms 3420 KB Output is correct
10 Correct 24 ms 3416 KB Output is correct
11 Correct 20 ms 3160 KB Output is correct
12 Correct 41 ms 3952 KB Output is correct
13 Correct 61 ms 6580 KB Output is correct
14 Correct 87 ms 7300 KB Output is correct
15 Correct 105 ms 8048 KB Output is correct
16 Correct 128 ms 10868 KB Output is correct
17 Correct 149 ms 11380 KB Output is correct
18 Correct 167 ms 12140 KB Output is correct
19 Correct 225 ms 13692 KB Output is correct
20 Correct 150 ms 11600 KB Output is correct