Submission #1053619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1053619	2024-08-11T14:29:16 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	151 ms	17236 KB

jobs

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << endl
#define all(x) x.begin(),x.end()

int n,d,m;
pii a[1000010];

bool ok(int x)
{
	int t=0,i=0,cnt=0,mx=0;
	while(i<m)
	{
		while(i<m && cnt<x && a[i].fi<=t) mx=max(mx,t-a[i].fi),i++,cnt++;
		cnt=0;
		t++;
	}
	return mx<=d;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>d>>m;
	for(int i=0;i<m;i++) cin>>a[i].fi;
	for(int i=0;i<m;i++) a[i].se=i;
	sort(a,a+m);
	int l=1,r=m,ans=m;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(ok(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<'\n';
	int t=1,i=0,cnt=0;
	while(i<m)
	{
		while(i<m && cnt<ans && a[i].fi<=t)
		{
			cout<<a[i].se+1<<' ';
			i++,cnt++;
		}
		cnt=0;
		t++;
		cout<<"0\n";
	}
	while(t<=n) 
	{
		t++;
		cout<<"0\n";
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3416 KB	Output is correct
2	Correct	10 ms	3472 KB	Output is correct
3	Correct	10 ms	3416 KB	Output is correct
4	Correct	10 ms	3508 KB	Output is correct
5	Correct	10 ms	3416 KB	Output is correct
6	Correct	10 ms	3420 KB	Output is correct
7	Correct	10 ms	3508 KB	Output is correct
8	Correct	10 ms	3420 KB	Output is correct
9	Correct	16 ms	3696 KB	Output is correct
10	Correct	17 ms	3672 KB	Output is correct
11	Correct	16 ms	3420 KB	Output is correct
12	Correct	31 ms	4692 KB	Output is correct
13	Correct	56 ms	7732 KB	Output is correct
14	Correct	65 ms	9300 KB	Output is correct
15	Correct	91 ms	9816 KB	Output is correct
16	Correct	113 ms	13684 KB	Output is correct
17	Correct	116 ms	14928 KB	Output is correct
18	Correct	128 ms	15184 KB	Output is correct
19	Correct	151 ms	17236 KB	Output is correct
20	Correct	120 ms	14928 KB	Output is correct