Submission #453126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453126	2021-08-04T08:12:06 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	54 / 100	314 ms	20132 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=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	26 ms	13184 KB	Execution killed with signal 11
2	Runtime error	26 ms	13092 KB	Execution killed with signal 11
3	Runtime error	26 ms	13072 KB	Execution killed with signal 11
4	Runtime error	25 ms	13128 KB	Execution killed with signal 11
5	Runtime error	32 ms	13084 KB	Execution killed with signal 11
6	Runtime error	25 ms	13064 KB	Execution killed with signal 11
7	Runtime error	33 ms	13116 KB	Execution killed with signal 11
8	Runtime error	25 ms	13072 KB	Execution killed with signal 11
9	Correct	41 ms	4800 KB	Output is correct
10	Correct	41 ms	4736 KB	Output is correct
11	Correct	32 ms	4492 KB	Output is correct
12	Correct	65 ms	6456 KB	Output is correct
13	Correct	96 ms	8944 KB	Output is correct
14	Correct	144 ms	11168 KB	Output is correct
15	Partially correct	174 ms	11956 KB	Partially correct
16	Correct	213 ms	13988 KB	Output is correct
17	Correct	243 ms	17952 KB	Output is correct
18	Correct	266 ms	18428 KB	Output is correct
19	Partially correct	314 ms	20132 KB	Partially correct
20	Correct	245 ms	18072 KB	Output is correct