Submission #1280404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280404		hanguyendanghuy	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	202 ms	29120 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=1e6+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];
struct h{
    ll a,id;
} b[MAXN];
bool cmp(h x,h y){
    return x.a<y.a;
}
bool check(ll dem){
    queue<ll> q;
    ll cur=m;
    for(i=n+k;i>=1;i--){
        while(cur>0&&b[cur].a==i)
            q.push(i-k),cur--;
        ll cnt=dem;
        while(cnt--&&q.size())
            q.pop();
        if(q.size()&&q.front()>=i){
            return false;
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>m;
    ll l=1,r=m,best=0;
    for(i=1;i<=m;i++)
        cin>>p,a[k+p]++,b[i].a=k+p,b[i].id=i;
    sort(b+1,b+m+1,cmp);
    while(l<r){
        ll m=(l+r)/2;
        if(check(m)){
            best=m;
            r=m;
        }
        else l=m+1;
    }
    if(check(l)) best=l;
    ll cur=1;
    for(i=1;i<=n+k;i++){
        ll cnt=0;
        while(cur<=m&&cnt<best&&b[cur].a-k<=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: 100 / 100