Submission #453099

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453099	2021-08-04T07:58:54 Z	Khizri	Job Scheduling (CEOI12_jobs)	C++17	30 / 100	335 ms	41288 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[mxn];
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

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	84 ms	27692 KB	Output isn't correct
2	Incorrect	35 ms	27740 KB	Output isn't correct
3	Incorrect	49 ms	27776 KB	Output isn't correct
4	Incorrect	51 ms	27712 KB	Output isn't correct
5	Incorrect	36 ms	27776 KB	Output isn't correct
6	Incorrect	44 ms	27720 KB	Output isn't correct
7	Incorrect	49 ms	27848 KB	Output isn't correct
8	Incorrect	35 ms	27720 KB	Output isn't correct
9	Correct	53 ms	25832 KB	Output is correct
10	Correct	52 ms	25852 KB	Output is correct
11	Correct	72 ms	25592 KB	Output is correct
12	Correct	97 ms	27748 KB	Output is correct
13	Correct	117 ms	30164 KB	Output is correct
14	Correct	171 ms	32208 KB	Output is correct
15	Runtime error	189 ms	33020 KB	Memory limit exceeded
16	Runtime error	259 ms	35164 KB	Memory limit exceeded
17	Runtime error	335 ms	39116 KB	Memory limit exceeded
18	Runtime error	294 ms	39724 KB	Memory limit exceeded
19	Runtime error	332 ms	41288 KB	Memory limit exceeded
20	Runtime error	280 ms	39140 KB	Memory limit exceeded