Submission #453077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453077	2021-08-04T07:52:47 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	213 ms	4124 KB

jobs

#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
	if(a>b) swap(a,b);
	if(a==0) return a+b;
	return gcd(b%a,a);
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
bool is_prime(ll n){
	ll k=sqrt(n);
	if(n==2) return true;
	if(n<2||n%2==0||k*k==n) return false;
	for(int i=3;i<=k;i+=2){
		if(n%i==0){
			return false;
		}
	}
	return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=1e6+5;
int t=1,n,d,m,arr[mxn];
bool check(int k){
	int x=1,say=0;
	for(int i=1;i<=m;i++){
		if(arr[i]>x){
			x=arr[i];
			say=1;
		}
		else{
			say++;
			if(x-arr[i]>d){
				return false;
			}
		}
		if(say>=k){
			say=0;
			x++;
		}
	}
	return true;
}
void solve(){
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++){
		cin>>arr[i];
	}
	sort(arr+1,arr+m+1);
	int l=1,r=n,ans=1;
	while(l<=r){
		int mm=(l+r)/2;
		if(check(mm)){
			r=mm-1;
			ans=mm;
		}
		else{
			l=mm+1;
		}
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		cout<<0<<endl;
	}
}
int main(){
	IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	844 KB	Output isn't correct
2	Incorrect	11 ms	880 KB	Output isn't correct
3	Incorrect	14 ms	848 KB	Output isn't correct
4	Incorrect	11 ms	844 KB	Output isn't correct
5	Incorrect	14 ms	920 KB	Output isn't correct
6	Incorrect	11 ms	828 KB	Output isn't correct
7	Incorrect	11 ms	844 KB	Output isn't correct
8	Incorrect	14 ms	844 KB	Output isn't correct
9	Correct	91 ms	1004 KB	Output is correct
10	Correct	23 ms	1076 KB	Output is correct
11	Correct	16 ms	844 KB	Output is correct
12	Correct	128 ms	1220 KB	Output is correct
13	Correct	81 ms	1672 KB	Output is correct
14	Correct	76 ms	2088 KB	Output is correct
15	Correct	82 ms	2480 KB	Output is correct
16	Correct	120 ms	2812 KB	Output is correct
17	Correct	130 ms	3268 KB	Output is correct
18	Correct	134 ms	3656 KB	Output is correct
19	Correct	213 ms	4124 KB	Output is correct
20	Correct	127 ms	3268 KB	Output is correct