Submission #1188241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188241		Francisco_Martin	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	287 ms	20940 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define debug(v) cerr<<#v" = "<<(v)<<"\n";
#define debugvec(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<v[i]<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define debugvecp(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<"[ "<<v[i].fst<<" "<<v[i].snd<<" ]"<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define fst first
#define snd second
#define gcd(x,y) __gcd(x,y)
#define OnlineJudge(s) freopen((s".in"),"r",stdin); freopen((s".out"),"w",stdout);
#define fastIO() cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit);
#define boolsolve() cout<<(solve()?"Yes":"No");

using ll=unsigned long long;
using ull=unsigned long long;
using pll=pair<ll,ll>;
using vll=vector<ll>;
using vpll=vector<pll>;
using vvll=vector<vll>;

const ll INF=1e18;
const ll MOD=1e9;
const ll MAXN=1e6;

void solve(){
    ll n, d, m;
    cin >> n >> d >> m;
    vpll A(m);
    for(int i=0; i<m; i++){
        cin >> A[i].fst;
        A[i].snd=i+1;
    }
    sort(A.begin(),A.end());
    auto ok=[&](ll k){
        queue<ll> q; ll z=0;
        for(int i=1; i<=n; i++){
            while(z<m && A[z].fst==i) q.push(A[z++].fst);
            if(!q.empty()){
                if(i-q.front()>d) return false;
                for(int j=0; j<k && !q.empty(); j++) q.pop();
            }
        }
        return q.empty();
    };
    ll l=0, r=INF;
    while(l<r){
        ll k=(l+r)/2;
        if(ok(k)) r=k;
        else l=k+1;
    }
    cout << l << "\n";
    queue<ll> q; ll z=0;
    for(int i=1; i<=n; i++){
        while(z<m && A[z].fst==i) q.push(A[z++].snd);
        for(int j=0; j<l && !q.empty(); j++){
            cout << q.front() << " ";
            q.pop();
        }
        cout << "0\n";
    }
}

int main(){
    fastIO();
    //OnlineJudge("")
    ll t=1;
    //cin >> t;
    while(t--){
        solve();
        //cout << "\n";
    }
    return 0;
}

• Subtask 1: 100 / 100