oj.uz

Submission #375277

# Submission time Handle Problem Language Result Execution time Memory
375277 2021-03-09T06:02:57 Z YJU Job Scheduling (CEOI12_jobs) C++14
95 / 100
 926 ms 35180 KB 
#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];
ll que[N];

bool ck(ll k){
	ll nl=0,nr=0;
	for(int i=1,id=1;i<=n;i++){
		while(id<=m&&st[lis[id]]==i)que[nr++]=(lis[id]),++id;
		REP(j,k){
			if(nr-nl==0)break;
			ans[que[nl++]]=i;
		}
		if(nr-nl&&st[que[nl]]+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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4076 KB Output is correct
2 Correct 32 ms 4076 KB Output is correct
3 Correct 35 ms 4076 KB Output is correct
4 Correct 32 ms 4076 KB Output is correct
5 Correct 32 ms 4100 KB Output is correct
6 Correct 33 ms 4076 KB Output is correct
7 Correct 32 ms 4076 KB Output is correct
8 Correct 33 ms 4204 KB Output is correct
9 Correct 45 ms 4332 KB Output is correct
10 Correct 44 ms 4332 KB Output is correct
11 Correct 44 ms 4076 KB Output is correct
12 Correct 99 ms 7944 KB Output is correct
13 Correct 166 ms 11756 KB Output is correct
14 Correct 278 ms 15724 KB Output is correct
15 Correct 356 ms 19456 KB Output is correct
16 Correct 487 ms 23404 KB Output is correct
17 Correct 645 ms 27116 KB Output is correct
18 Correct 798 ms 31084 KB Output is correct
19 Runtime error 926 ms 35180 KB Memory limit exceeded
20 Correct 649 ms 27244 KB Output is correct