Submission #744290

#	Time	Username	Problem	Language	Result	Execution time	Memory
744290		MODDI	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	482 ms	13884 KiB

jobs

#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 / 100