Submission #858423

#TimeUsernameProblemLanguageResultExecution timeMemory
858423ilefJob Scheduling (CEOI12_jobs)C++14
0 / 100
96 ms4948 KiB
#include <bits/stdc++.h>
using namespace std;
const int M=3e5+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 true;
}

int main() {
	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=0;
	int r=m;
	while(l+1<r){
	    int mid=(l+r)/2;
	    if(good(mid)){
	        r=mid;
	    }
	    else{
	        l=mid;
	    }
	}
	int cnt=0;
	cout<<r<<endl;
	for(int i=0;i<m;i++){
	    if(cnt==r){
	        cout<<0<<endl;
	        cnt=0;
	    }
	    cout<<a[i].second+1<<" ";
	   
	    cnt++;
	}
	cout<<0<<endl;
	cout<<0<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...