Submission #681725

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
681725	2023-01-13T23:51:29 Z	chezpotato	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	1000 ms	25060 KB

jobs

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

int n , d , m;
vector<pair<int , int>> jobs;

//for a given number of machines, check if it works
bool valid(int machines){
    priority_queue<int, vector<int> , greater<int>> endTimes;
    for(int i=0; i<machines; i++){
        endTimes.push(jobs[i].first);
    }
    for(int i=machines; i<m; i++){
        int newEndTime = max(endTimes.top() + 1 , jobs[i].first);
        if(newEndTime - jobs[i].first > d) return false;
        endTimes.push(newEndTime);
        endTimes.pop();
    }
    return true;
}

//we want the MINIMUM number of machines, so use first_true
int binarySearch(int lo, int hi){
    hi++;
    while(lo < hi){
        int mid = lo + (hi - lo)/2;
        if(valid(mid)){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    return lo;
}

int main(){
    //freopen("job.in" , "r" , stdin);
    
    cin >> n >> d >> m; jobs.resize(m);

    for(int i=0; i<m; i++){
        cin >> jobs[i].first;
        jobs[i].second = i+1;
    }

    sort(jobs.begin() , jobs.end());
    int minMachines = binarySearch(1 , m);

    cout << minMachines << endl;

    map<int , vector<int>> schedule;
    priority_queue<int, vector<int> , greater<int>> endTimes;
    for(int i=0; i<minMachines; i++){
        endTimes.push(jobs[i].first);
        schedule[jobs[i].first].push_back(jobs[i].second);
    }
    for(int i=minMachines; i<m; i++){
        int newEndTime = max(endTimes.top() + 1 , jobs[i].first);
        schedule[newEndTime].push_back(jobs[i].second);
        endTimes.push(newEndTime);
        endTimes.pop();
    }

    for(int i=1; i<=n; i++){
        for(const int x : schedule[i]){
            cout << x << " ";
        }
        cout << 0 << endl;
    }

}

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	3340 KB	Output is correct
2	Correct	94 ms	3276 KB	Output is correct
3	Correct	87 ms	3312 KB	Output is correct
4	Correct	84 ms	3428 KB	Output is correct
5	Correct	83 ms	3316 KB	Output is correct
6	Correct	83 ms	3264 KB	Output is correct
7	Correct	101 ms	3308 KB	Output is correct
8	Correct	85 ms	3308 KB	Output is correct
9	Correct	238 ms	10468 KB	Output is correct
10	Correct	240 ms	10500 KB	Output is correct
11	Correct	95 ms	2580 KB	Output is correct
12	Correct	209 ms	4992 KB	Output is correct
13	Correct	301 ms	7792 KB	Output is correct
14	Correct	462 ms	11476 KB	Output is correct
15	Correct	527 ms	11604 KB	Output is correct
16	Correct	692 ms	15460 KB	Output is correct
17	Correct	829 ms	19776 KB	Output is correct
18	Correct	926 ms	19876 KB	Output is correct
19	Execution timed out	1086 ms	25060 KB	Time limit exceeded
20	Correct	842 ms	19904 KB	Output is correct