Submission #934438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934438	2024-02-27T10:21:04 Z	tamir1	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	211 ms	21300 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 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	3204 KB	Output is correct
3	Correct	17 ms	3420 KB	Output is correct
4	Correct	13 ms	3160 KB	Output is correct
5	Correct	13 ms	3160 KB	Output is correct
6	Correct	13 ms	3164 KB	Output is correct
7	Correct	14 ms	3164 KB	Output is correct
8	Correct	13 ms	3164 KB	Output is correct
9	Correct	24 ms	3420 KB	Output is correct
10	Correct	26 ms	3420 KB	Output is correct
11	Correct	20 ms	3164 KB	Output is correct
12	Correct	40 ms	5776 KB	Output is correct
13	Correct	67 ms	8784 KB	Output is correct
14	Correct	87 ms	9296 KB	Output is correct
15	Correct	103 ms	12148 KB	Output is correct
16	Correct	134 ms	14780 KB	Output is correct
17	Correct	163 ms	17784 KB	Output is correct
18	Correct	175 ms	20356 KB	Output is correct
19	Correct	211 ms	21300 KB	Output is correct
20	Correct	152 ms	17788 KB	Output is correct