Submission #748645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
748645	2023-05-26T16:52:16 Z	mariowong	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	279 ms	14836 KB

jobs

#include <bits/stdc++.h>
using namespace std;
 
int n,d,m,l,r,mid,ct,pt,now;
pair <int,int> a[1000005]; 	
bool ok;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> d >> m;
	for (int i=1;i<=m;i++){
		cin >> a[i].first;
		a[i].second=i;
	}
	sort(a+1,a+1+m);
	l=1; r=m; 
	while (l < r){
		mid=(l+r)/2; ct=0;
		ok=true; pt=0;
		for (int i=1;i<=n;i++){
			now=0;
			while (now < mid && pt+1 <= m && a[pt+1].first <= i){
				pt++; now++;
				if (i > a[pt].first+d){
					pt=-1;
					goto out;
				}
			}
		} 
		out:;
		if (pt == m)
		r=mid;
		else
		l=mid+1;
	}
	cout << l << "\n"; pt=0;
	for (int i=1;i<=n;i++){
		now=0;
		while (now < l && pt+1 <= m && a[pt+1].first <= i){
			pt++; now++;
			cout << a[pt].second << " "; 
			if (i > a[pt].first+d){
				pt=-1;
				goto out;
			}
		}
		cout << "0\n";
	} 
	return 0;
}	

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	2004 KB	Output is correct
2	Correct	22 ms	2116 KB	Output is correct
3	Correct	20 ms	1908 KB	Output is correct
4	Correct	22 ms	1908 KB	Output is correct
5	Correct	20 ms	1936 KB	Output is correct
6	Correct	19 ms	1900 KB	Output is correct
7	Correct	23 ms	1944 KB	Output is correct
8	Correct	20 ms	1920 KB	Output is correct
9	Correct	33 ms	2072 KB	Output is correct
10	Correct	33 ms	2024 KB	Output is correct
11	Correct	28 ms	2064 KB	Output is correct
12	Correct	57 ms	3640 KB	Output is correct
13	Correct	82 ms	5164 KB	Output is correct
14	Correct	128 ms	7056 KB	Output is correct
15	Correct	145 ms	8588 KB	Output is correct
16	Correct	185 ms	10236 KB	Output is correct
17	Correct	215 ms	11772 KB	Output is correct
18	Correct	237 ms	13112 KB	Output is correct
19	Correct	279 ms	14836 KB	Output is correct
20	Correct	215 ms	11556 KB	Output is correct