Submission #858472

#	Time	Username	Problem	Language	Result	Execution time	Memory
858472		ilef	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	196 ms	13888 KiB

jobs

#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;
         }
         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;
}

• Subtask 1: 90 / 100