Submission #792383

#	Time	Username	Problem	Language	Result	Execution time	Memory
792383		MON	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	109 ms	10736 KiB

jobs

#include<bits/stdc++.h>
using namespace std;

bool func(int arr[], int m, int n, int nummachines, int maxdelay){
	bool res = true;
	int curpos = 0;
	for(int i=1; i<=n; i++){
		if(curpos>=m || !res){
			break;
		}
		else{
			int temp=curpos;
			for(int j=curpos; j<min(curpos+nummachines, m); j++){
				if(arr[j]<=i){
					temp++;
					if(i-arr[j]>maxdelay){
						res = false;
						break;
					}
				}
				else{
					break;
				}
			}
			curpos = temp;
		}
	}
	return curpos==m && res;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, d, m;
	cin >> n >> d >> m;
	int arr[m];
	for(int i=0; i<m; i++){
		cin >> arr[i];
	}
	vector<int> arr2[n];
	for(int i=0; i<m; i++){
		arr2[arr[i]-1].push_back(i+1);
	}
	sort(arr, arr+m);
	int minmachine = 0;
	int maxmachine = m;
	while(minmachine<maxmachine){
		int mid = (minmachine+maxmachine)/2;
		bool res = func(arr, m, n, mid, d);
		if(!res){
			minmachine = mid+1;
		}
		else{
			maxmachine = mid;
		}
	}
	cout << minmachine << '\n';
	for(int i = 1; i <= n ; i++) cout << "0\n";
	return 0;
}

• Subtask 1: 100 / 100