Submission #1280392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280392		hanguyendanghuy	Job Scheduling (CEOI12_jobs)	C++20	20 / 100	75 ms	9804 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
constexpr ll MAXN=2e5+5,MAXV=3e5,MOD=1e9+7,INF=1e18;
ll n,m,i,j,p,k,ans,a[MAXN],dem,st,en;
vector<ll> day[MAXN];
bool check(ll m){
    ll cnt=0;
    for(ll i=n+k;i>=1;i--){
        cnt=max(0ll,cnt+(a[i]-m));
    }
    if(cnt>0) return false;
    return true;
}
struct h{
    ll a,id;
} b[MAXN];
bool cmp(h x,h y){
    return x.a<y.a;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>m;
    ll l=1,r=n,best=0;
    for(i=1;i<=m;i++)
        cin>>p,a[k+p]++,b[i].a=k+p,b[i].id=i;
    while(l<r){
        ll m=(l+r)/2;
        if(check(m)){
            best=m;
            r=m;
        }
        else l=m+1;
    }
    if(check(l)) best=l;
    sort(b+1,b+m+1,cmp);
    ll cur=m;
    for(i=n+k;i>=1;i--){
        ll cnt=0;
        while(cur>0&&cnt<best&&b[cur].a>=i){
            day[i].pb(b[cur].id);
            cur--;
            cnt++;
        }
    }
    cout<<best<<'\n';
    for(i=1;i<=n;i++){
        for(ll x:day[i])
            cout<<x<<" ";
        cout<<0<<'\n';
    }
}

• Subtask 1: 20 / 100