Submission #453160

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453160	2021-08-04T08:25:35 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	313 ms	16992 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;
vector<pii>arr;
vector<int>vt[100005];
bool check(int k){
	int x=1,say=0;
	for(int i=0;i<m;i++){
		if(arr[i].F>x){
			x=arr[i].F;
			say=1;
		}
		else{
			say++;
			if(x-arr[i].F>d){
				return false;
			}
		}
		if(say>=k){
			say=0;
			x++;
		}
	}
	return true;
}
void f(int k){
	int say=0,ind=0;
	for(int x=1;x<=n;x++){
		say=0;
		while(ind<m&&arr[ind].F<=x&&say<k){
			cout<<arr[ind].S<<' ';
			ind++;
			say++;
		}
		cout<<0<<endl;
	}
}
void solve(){
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++){
		int q;
		cin>>q;
		arr.pb({q,i});
	}
	sort(all(arr));
	int l=0,r=n,ans=0;
	while(l<=r){
		int mm=(l+r)/2;
		if(check(mm)){
			r=mm-1;
			ans=mm;
		}
		else{
			l=mm+1;
		}
	}
	cout<<ans<<endl;
	f(ans);
}
int main(){
	IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	17 ms	4044 KB	Output isn't correct
2	Incorrect	15 ms	4080 KB	Output isn't correct
3	Incorrect	15 ms	4044 KB	Output isn't correct
4	Incorrect	16 ms	4044 KB	Output isn't correct
5	Incorrect	15 ms	4044 KB	Output isn't correct
6	Incorrect	15 ms	4044 KB	Output isn't correct
7	Incorrect	15 ms	4044 KB	Output isn't correct
8	Incorrect	15 ms	4044 KB	Output isn't correct
9	Correct	42 ms	4696 KB	Output is correct
10	Correct	42 ms	4560 KB	Output is correct
11	Correct	33 ms	4416 KB	Output is correct
12	Correct	64 ms	6140 KB	Output is correct
13	Correct	95 ms	7732 KB	Output is correct
14	Correct	144 ms	9264 KB	Output is correct
15	Correct	165 ms	10752 KB	Output is correct
16	Correct	205 ms	12456 KB	Output is correct
17	Correct	240 ms	13900 KB	Output is correct
18	Correct	261 ms	15304 KB	Output is correct
19	Correct	313 ms	16992 KB	Output is correct
20	Correct	234 ms	13796 KB	Output is correct