Submission #744504

#	Time	Username	Problem	Language	Result	Execution time	Memory
744504		alecurse	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	387 ms	13736 KiB

jobs

#include <iostream>
#include <vector>
#define mp make_pair
#include <unordered_map>
#include <algorithm>
using namespace std;
int N,D,M;
vector<pair<int,int> > v;

bool isok(int k) {
    int indexi=0;
    int indexj=0;
    for(int 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;
}
int bsearch() {
    int a=1,b=2*1e5;
    unordered_map<int,bool> m;
    while(a<=b) {
        int 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(int i=0;i<M;i++) {
        cin>>v[i].first;
        v[i].second=i;
    }
    sort(v.begin(), v.end());
    int sol=bsearch();
    cout<<bsearch()<<"\n";
    int indexi=0;
    int indexj=0;
    for(int 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";
    }
}

• Subtask 1: 60 / 100