Submission #453131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453131	2021-08-04T08:13:26 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	54 / 100	312 ms	20100 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 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=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;
		}
	}
	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	24 ms	13128 KB	Execution killed with signal 11
2	Runtime error	31 ms	13092 KB	Execution killed with signal 11
3	Runtime error	32 ms	13060 KB	Execution killed with signal 11
4	Runtime error	32 ms	13136 KB	Execution killed with signal 11
5	Runtime error	25 ms	13140 KB	Execution killed with signal 11
6	Runtime error	30 ms	13088 KB	Execution killed with signal 11
7	Runtime error	25 ms	13124 KB	Execution killed with signal 11
8	Runtime error	26 ms	13068 KB	Execution killed with signal 11
9	Correct	40 ms	4792 KB	Output is correct
10	Correct	40 ms	4772 KB	Output is correct
11	Correct	32 ms	4544 KB	Output is correct
12	Correct	66 ms	6536 KB	Output is correct
13	Correct	97 ms	9008 KB	Output is correct
14	Correct	159 ms	11184 KB	Output is correct
15	Partially correct	160 ms	11952 KB	Partially correct
16	Correct	212 ms	14016 KB	Output is correct
17	Correct	241 ms	18052 KB	Output is correct
18	Correct	264 ms	18472 KB	Output is correct
19	Partially correct	312 ms	20100 KB	Partially correct
20	Correct	252 ms	18084 KB	Output is correct