Submission #792384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792384	2023-07-25T03:55:48 Z	MON	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	101 ms	10828 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1496 KB	Output is correct
2	Correct	8 ms	1476 KB	Output is correct
3	Correct	11 ms	1496 KB	Output is correct
4	Correct	8 ms	1496 KB	Output is correct
5	Correct	8 ms	1496 KB	Output is correct
6	Correct	10 ms	1496 KB	Output is correct
7	Correct	8 ms	1496 KB	Output is correct
8	Correct	10 ms	1608 KB	Output is correct
9	Correct	11 ms	3796 KB	Output is correct
10	Correct	12 ms	3832 KB	Output is correct
11	Correct	11 ms	1236 KB	Output is correct
12	Correct	23 ms	2132 KB	Output is correct
13	Correct	34 ms	3664 KB	Output is correct
14	Correct	75 ms	4692 KB	Output is correct
15	Correct	56 ms	5304 KB	Output is correct
16	Correct	96 ms	6864 KB	Output is correct
17	Correct	101 ms	8428 KB	Output is correct
18	Correct	91 ms	8164 KB	Output is correct
19	Correct	99 ms	10828 KB	Output is correct
20	Correct	97 ms	8432 KB	Output is correct