Submission #375274

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375274	2021-03-09T06:00:46 Z	YJU	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	1000 ms	23916 KB

jobs

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=1e6+5;
const ll MOD=1e9+7;
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,st[N],d,m,ans[N],lis[N];
queue<ll> que;

bool ck(ll k){
	while(SZ(que))que.pop();
	for(int i=1,id=1;i<=n;i++){
		while(id<=m&&st[lis[id]]==i)que.push(lis[id]),++id;
		REP(j,k){
			if(!SZ(que))break;
			ans[que.front()]=i;
			que.pop();
		}
		if(SZ(que)&&st[que.front()]+d<=i)return 0;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>d>>m;
	REP1(i,m){
        cin>>st[i];
        lis[i]=i;
	}
	sort(lis+1,lis+m+1,[&](ll a,ll b){
		return (st[a]<st[b]);
	});
	//REP1(i,m)cout<<lis[i]<<st[lis[i]]<<"\n";
	ll r=m,l=-1;
	while(l<r-1){
		ll mid=(l+r)>>1;
		if(ck(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<r<<"\n";
	ck(r);

	sort(lis+1,lis+m+1,[&](ll a,ll b){
        return (ans[a]<ans[b]);
	});

	//REP1(i,m)cout<<lis[i]<<" "<<ans[lis[i]]<<"\n";

	for(int i=1,id=1;i<=n;i++){
		while(id<=m&&ans[lis[id]]==i)cout<<lis[id]<<" ",++id;
		cout<<"0\n";
	}
	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4


*/

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	4204 KB	Output is correct
2	Correct	42 ms	4204 KB	Output is correct
3	Correct	37 ms	4204 KB	Output is correct
4	Correct	38 ms	4204 KB	Output is correct
5	Correct	37 ms	4204 KB	Output is correct
6	Correct	37 ms	4204 KB	Output is correct
7	Correct	45 ms	4204 KB	Output is correct
8	Correct	39 ms	4224 KB	Output is correct
9	Correct	56 ms	3564 KB	Output is correct
10	Correct	53 ms	3692 KB	Output is correct
11	Correct	53 ms	3308 KB	Output is correct
12	Correct	117 ms	6508 KB	Output is correct
13	Correct	235 ms	9708 KB	Output is correct
14	Correct	432 ms	12908 KB	Output is correct
15	Correct	577 ms	15468 KB	Output is correct
16	Correct	701 ms	18728 KB	Output is correct
17	Correct	947 ms	23788 KB	Output is correct
18	Execution timed out	1091 ms	21724 KB	Time limit exceeded
19	Execution timed out	1095 ms	23916 KB	Time limit exceeded
20	Correct	932 ms	23788 KB	Output is correct