Submission #744508

#TimeUsernameProblemLanguageResultExecution timeMemory
744508alecurseJob Scheduling (CEOI12_jobs)C++14
60 / 100
381 ms20704 KiB
#include <iostream>
#include <vector>
#define mp make_pair
#include <unordered_map>
#define ll long long int
#include <algorithm>
using namespace std;
ll N,D,M;
vector<pair<ll,ll> > v;

bool isok(ll k) {
    ll indexi=0;
    ll indexj=0;
    for(ll i=0;i<M;i++) {
        if(indexj==k||v[i].first>indexi+1) {
            indexi++;
            indexj=0;
            if(indexi>=N) return false;
        }   
        if(indexi+1-v[i].first>D) return false;
        indexj++;
    }
    return true;
}
ll bsearch() {
    ll a=1,b=1e7;
    unordered_map<ll,bool> m;
    while(a<=b) {
        ll k=(a+b)/2;
        m[k]=isok(k);
        if(m[k]&&(k==1||(m.count(k-1)&&!m[k-1]))) return k;
        if(!m[k]&&m.count(k+1)&&m[k+1]) return k+1;
        if(m[k]) b=k-1;
        else a=k+1;
    }
    return -1;
}


int main() {
    cin>>N>>D>>M;
    v.resize(M);
    for(ll i=0;i<M;i++) {
        cin>>v[i].first;
        v[i].second=i;
    }
    sort(v.begin(), v.end());
    ll sol=bsearch();
    cout<<bsearch()<<"\n";
    ll indexi=0;
    ll indexj=0;
    for(ll i=0;i<M;i++) {
        if(indexj==sol||v[i].first>indexi+1) {
            indexi++;
            indexj=0;
            cout<<0<<"\n";
        }   
        cout<<v[i].second+1<<" ";
        indexj++;
    }
    cout<<0<<'\n';
    while(indexi<N-1) {
        indexi++;
        cout<<0<<"\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...