Submission #453116

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453116	2021-08-04T08:07:43 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	54 / 100	334 ms	20172 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||x>n){
				return false;
			}
		}
		if(say>=k){
			say=0;
			x++;
		}
	}
	return true;
}
void f(int k){
	int x=1,say=0;
	for(int i=0;i<m;i++){
		if(arr[i].F>x){
			x=arr[i].F;
			vt[x].pb(arr[i].S);
		}
		else{
			say++;
			vt[x].pb(arr[i].S);
		}
		if(say>=k){
			say=0;
			x++;
		}
	}
}
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=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;
		}
	}
	f(ans);
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		for(int v:vt[i]){
			cout<<v<<' ';
		}
		cout<<0<<endl;
	}
}
int main(){
	IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1

54.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	27 ms	13072 KB	Execution killed with signal 11
2	Runtime error	27 ms	13100 KB	Execution killed with signal 11
3	Runtime error	29 ms	13048 KB	Execution killed with signal 11
4	Runtime error	28 ms	13088 KB	Execution killed with signal 11
5	Runtime error	26 ms	13136 KB	Execution killed with signal 11
6	Runtime error	27 ms	13124 KB	Execution killed with signal 11
7	Runtime error	27 ms	13048 KB	Execution killed with signal 11
8	Runtime error	29 ms	13056 KB	Execution killed with signal 11
9	Correct	55 ms	4772 KB	Output is correct
10	Correct	48 ms	4796 KB	Output is correct
11	Correct	57 ms	4516 KB	Output is correct
12	Correct	74 ms	6556 KB	Output is correct
13	Correct	100 ms	8956 KB	Output is correct
14	Correct	200 ms	11292 KB	Output is correct
15	Partially correct	181 ms	11880 KB	Partially correct
16	Correct	243 ms	14040 KB	Output is correct
17	Correct	249 ms	18028 KB	Output is correct
18	Correct	280 ms	18560 KB	Output is correct
19	Partially correct	334 ms	20172 KB	Partially correct
20	Correct	253 ms	18008 KB	Output is correct