Submission #934414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934414	2024-02-27T10:02:24 Z	tamir1	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	198 ms	21380 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=1,j,day=0;
	while(i<=m){
		day++;
		for(j=i;j<i+mid && j<=m;j++){
			if(day>a[j].ff+d) return 0;
		}
		i=j;
	}
	if(day>n) return 0;
	return 1;
}
void solve(ll x){
	ll i,j,day=0;
	for(i=1;i<=m;){
		day++;
		for(j=i;j<i+x && j<=m;j++){
			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

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	17 ms	3164 KB	Output isn't correct
2	Incorrect	13 ms	3164 KB	Output isn't correct
3	Incorrect	13 ms	3160 KB	Output isn't correct
4	Incorrect	13 ms	3164 KB	Output isn't correct
5	Incorrect	13 ms	3416 KB	Output isn't correct
6	Incorrect	15 ms	3164 KB	Output isn't correct
7	Incorrect	13 ms	3164 KB	Output isn't correct
8	Incorrect	13 ms	3164 KB	Output isn't correct
9	Correct	24 ms	3420 KB	Output is correct
10	Correct	24 ms	3456 KB	Output is correct
11	Correct	20 ms	3164 KB	Output is correct
12	Correct	40 ms	5968 KB	Output is correct
13	Correct	62 ms	8564 KB	Output is correct
14	Correct	85 ms	9344 KB	Output is correct
15	Incorrect	106 ms	12148 KB	Output isn't correct
16	Correct	127 ms	14932 KB	Output is correct
17	Correct	152 ms	17792 KB	Output is correct
18	Correct	184 ms	20356 KB	Output is correct
19	Correct	198 ms	21380 KB	Output is correct
20	Correct	152 ms	17748 KB	Output is correct