Submission #754069

#	Time	Username	Problem	Language	Result	Execution time	Memory
754069		textot	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1069 ms	22296 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000000
#define int long long
struct request{
    int day;
    int id;
};
bool sortbyday(request &r1, request &r2){
    return r1.day<r2.day;
}
int numreqs, numdays, maxdelay; 
request jobreqs[MAXN];
bool works(int nummach){
    int day = 1;
    //check jobreqs by chucks of size nummach and see if any of the jobs are overdue
    while(numreqs>(day-1)*nummach){
        for(int i = 0; i < nummach; i++){
            if(jobreqs[(day-1)*nummach+i].day<day-maxdelay){ //overdue job check
                return false;
            }
        }
        day++;

    }
    return true;
}
signed main(){
    cin>>numdays>>maxdelay>>numreqs;
    int day;
    for(int i = 1; i <= numreqs; i++){
        cin>>day;
        jobreqs[i-1] = {day, i};
    }
    sort(jobreqs, jobreqs+numreqs, sortbyday);
    int lo = 1, hi = MAXN;
    while(lo!=hi){
        int mid = (lo+hi)/2;
        if(works(mid)){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    cout<<lo<<endl;
    int index = 0;
    for(int i = 0; i < numdays; i++){
        for(int j = 0; j < lo; j++){
            if(index < numreqs){
                cout<<jobreqs[index].id<<" ";
                index++;
            }
        }
        cout<<0<<endl;

    }


}

• Subtask 1: 0 / 100