Submission #1155070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155070		AlgorithmWarrior	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	201 ms	13640 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e6+5;
int n,d,m;
struct request{
    int day,pos;
    bool operator<(request ot){
        return day<ot.day;
    }
}req[MAX];
int capacity;

void read(){
    cin>>n>>d>>m;
    int i;
    for(i=1;i<=m;++i){
        cin>>req[i].day;
        req[i].pos=i;
    }
    sort(req+1,req+m+1);
}

bool check(int cap){
    int i;
    int id=1;
    for(i=1;i<=n;++i){
        int used=0;
        while(id<=m && used<cap && req[id].day<=i){
            ++used;
            ++id;
        }
        if(id<=m && req[id].day+d==i)
            return 0;
    }
    return 1;
}

int bin_search(){
    /// (]
    int st=0,dr=m;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(mij))
            dr=mij;
        else
            st=mij;
    }
    capacity=dr;
    return dr;
}

void plan_work(){
    int i;
    int id=1;
    for(i=1;i<=n;++i){
        int used=0;
        while(id<=m && used<capacity && req[id].day<=i){
            cout<<req[id].pos<<' ';
            ++used;
            ++id;
        }
        cout<<"0\n";
    }
}

int main()
{
    read();
    cout<<bin_search()<<'\n';
    plan_work();
    return 0;
}

• Subtask 1: 100 / 100