Submission #934434

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934434	2024-02-27T10:19:12 Z	tamir1	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	201 ms	21372 KB

jobs

#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
using namespace std;
ll i,n,d,m,l,r,mid,ans;
pair<ll,ll> a[1000005];
bool check(ll mid){
	ll i,j,day=0;
	i=1;
	while(i<=m){
		day++;
		for(j=i;j<i+mid && j<=m;j++){
			if(a[j].ff>day) break;
			if(day>a[j].ff+d) return 0;
		}
		i=j;
	}
	return 1;
}
void solve(ll x){
	ll i,j,day=0;
	i=1;
	while(i<=m){
		day++;
		for(j=i;j<i+x && j<=m;j++){
			if(a[j].ff>day) break;
			cout << a[j].ss << " ";
		}
		i=j;
		cout << 0 << "\n";
	}
	for(i=day+1;i<=n;i++){
		cout << 0 << "\n";
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> d >> m;
	for(i=1;i<=m;i++){
		cin >> a[i].ff;
		a[i].ss=i;
	}
	sort(a+1,a+m+1);
	l=1;
	r=m;
	while(r-l>1){
		mid=(r+l+1)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	if(check(l)) ans=l;
	else if(check(r)) ans=r;
	cout << ans << "\n";
	solve(ans);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3160 KB	Output is correct
2	Correct	13 ms	3208 KB	Output is correct
3	Correct	13 ms	3208 KB	Output is correct
4	Correct	13 ms	3164 KB	Output is correct
5	Correct	13 ms	3164 KB	Output is correct
6	Correct	13 ms	3164 KB	Output is correct
7	Correct	13 ms	3164 KB	Output is correct
8	Correct	14 ms	3164 KB	Output is correct
9	Correct	27 ms	3432 KB	Output is correct
10	Correct	24 ms	3416 KB	Output is correct
11	Correct	20 ms	3160 KB	Output is correct
12	Correct	41 ms	5972 KB	Output is correct
13	Correct	62 ms	8560 KB	Output is correct
14	Correct	94 ms	9552 KB	Output is correct
15	Correct	104 ms	12164 KB	Output is correct
16	Correct	130 ms	14932 KB	Output is correct
17	Correct	155 ms	17776 KB	Output is correct
18	Correct	168 ms	20352 KB	Output is correct
19	Correct	201 ms	21372 KB	Output is correct
20	Correct	153 ms	17972 KB	Output is correct