Submission #792383

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792383	2023-07-25T03:55:27 Z	MON	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	109 ms	10736 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	10 ms	1496 KB	Output is correct
3	Correct	10 ms	1476 KB	Output is correct
4	Correct	8 ms	1496 KB	Output is correct
5	Correct	8 ms	1496 KB	Output is correct
6	Correct	8 ms	1496 KB	Output is correct
7	Correct	7 ms	1496 KB	Output is correct
8	Correct	8 ms	1604 KB	Output is correct
9	Correct	11 ms	3852 KB	Output is correct
10	Correct	12 ms	3824 KB	Output is correct
11	Correct	13 ms	1236 KB	Output is correct
12	Correct	24 ms	2124 KB	Output is correct
13	Correct	35 ms	3728 KB	Output is correct
14	Correct	56 ms	4748 KB	Output is correct
15	Correct	55 ms	5208 KB	Output is correct
16	Correct	87 ms	6884 KB	Output is correct
17	Correct	98 ms	8436 KB	Output is correct
18	Correct	99 ms	8168 KB	Output is correct
19	Correct	101 ms	10736 KB	Output is correct
20	Correct	109 ms	8524 KB	Output is correct