Submission #788399

#	Time	Username	Problem	Language	Result	Execution time	Memory
788399		Sandarach151	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	165 ms	27572 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';
	vector<pair<int, int>> vect;
	for(int i=0; i<n; i++){
		for(int j=0; j<arr2[i].size(); j++){
			vect.push_back({arr2[i][j], i});
		}
	}
	int pos = 0;
	for(int i=0; i<n; i++){
		int temp = pos;
		while(pos<min(temp+minmachine, m) && vect[pos].second<=i){
			cout << vect[pos].first << ' ';
			pos++;
		}
		cout << 0 << '\n';
	}		
	return 0;
}
	

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int j=0; j<arr2[i].size(); j++){
      |                ~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100