Submission #453081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453081	2021-08-04T07:54:05 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	158 ms	3952 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||x>n){
				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	656 KB	Output isn't correct
2	Incorrect	11 ms	716 KB	Output isn't correct
3	Incorrect	11 ms	716 KB	Output isn't correct
4	Incorrect	11 ms	716 KB	Output isn't correct
5	Incorrect	11 ms	684 KB	Output isn't correct
6	Incorrect	11 ms	716 KB	Output isn't correct
7	Incorrect	11 ms	716 KB	Output isn't correct
8	Incorrect	11 ms	732 KB	Output isn't correct
9	Correct	22 ms	844 KB	Output is correct
10	Correct	25 ms	876 KB	Output is correct
11	Correct	21 ms	716 KB	Output is correct
12	Correct	32 ms	972 KB	Output is correct
13	Correct	59 ms	1400 KB	Output is correct
14	Correct	78 ms	1868 KB	Output is correct
15	Correct	79 ms	2264 KB	Output is correct
16	Correct	114 ms	2732 KB	Output is correct
17	Correct	126 ms	3012 KB	Output is correct
18	Correct	129 ms	3396 KB	Output is correct
19	Correct	158 ms	3952 KB	Output is correct
20	Correct	129 ms	3040 KB	Output is correct