Submission #260552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
260552	2020-08-10T14:05:02 Z	kshitij_sodani	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	423 ms	16984 KB

jobs

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
int n,d;
int m;
vector<int> ac[100001];
bool check(int mid,int xx=0){
	int cur=1;
	int le=mid;
	for(int j=1;j<=n;j++){

		for(auto jj:ac[j]){
			
			if(cur>j+d){
				return false;
			}
			le-=1;
			if(xx){
				cout<<jj+1<<" ";
			}
			if(le==0){
				if(xx){
					cout<<0<<endl;
				}
				cur+=1;
				le=mid;
			}
			
		}
		if(cur==j){
			if(xx){
				cout<<0<<endl;
			}
			cur+=1;
			le=mid;
		}
	}


}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>d>>m;
	for(int i=0;i<m;i++){
		int bb;
		cin>>bb;
		ac[bb].pb(i);
	}
	int low=1;
	int high=m;
	while(low<high-1){
		int mid=(low+high)/2;
		if(check(mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	int ans=high;
	if(check(low)){
		ans=min(ans,low);
	}
	cout<<ans<<endl;
	check(ans,1);








	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'bool check(int, int)':
jobs.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	4092 KB	Output is correct
2	Correct	43 ms	4092 KB	Output is correct
3	Correct	44 ms	4092 KB	Output is correct
4	Correct	43 ms	4092 KB	Output is correct
5	Correct	44 ms	4156 KB	Output is correct
6	Correct	43 ms	4084 KB	Output is correct
7	Correct	43 ms	4084 KB	Output is correct
8	Correct	44 ms	4092 KB	Output is correct
9	Correct	240 ms	4644 KB	Output is correct
10	Correct	239 ms	4344 KB	Output is correct
11	Correct	26 ms	4224 KB	Output is correct
12	Correct	49 ms	5752 KB	Output is correct
13	Correct	71 ms	8056 KB	Output is correct
14	Correct	132 ms	9976 KB	Output is correct
15	Correct	116 ms	11000 KB	Output is correct
16	Correct	185 ms	13688 KB	Output is correct
17	Correct	219 ms	15996 KB	Output is correct
18	Correct	223 ms	15712 KB	Output is correct
19	Correct	423 ms	16984 KB	Output is correct
20	Correct	241 ms	16120 KB	Output is correct