Submission #453121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453121	2021-08-04T08:11:15 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	17 / 100	322 ms	20076 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+d>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

17.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	26 ms	13124 KB	Execution killed with signal 11
2	Runtime error	25 ms	13168 KB	Execution killed with signal 11
3	Runtime error	25 ms	13120 KB	Execution killed with signal 11
4	Runtime error	33 ms	13048 KB	Execution killed with signal 11
5	Runtime error	26 ms	13108 KB	Execution killed with signal 11
6	Runtime error	25 ms	13088 KB	Execution killed with signal 11
7	Runtime error	29 ms	13080 KB	Execution killed with signal 11
8	Runtime error	25 ms	13172 KB	Execution killed with signal 11
9	Correct	42 ms	4744 KB	Output is correct
10	Correct	49 ms	4760 KB	Output is correct
11	Incorrect	33 ms	4544 KB	Output isn't correct
12	Incorrect	66 ms	6416 KB	Output isn't correct
13	Incorrect	98 ms	8940 KB	Output isn't correct
14	Incorrect	142 ms	10716 KB	Output isn't correct
15	Incorrect	163 ms	11896 KB	Output isn't correct
16	Incorrect	211 ms	14080 KB	Output isn't correct
17	Incorrect	249 ms	17748 KB	Output isn't correct
18	Correct	298 ms	18544 KB	Output is correct
19	Partially correct	322 ms	20076 KB	Partially correct
20	Incorrect	275 ms	17748 KB	Output isn't correct