답안 #681732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681732	2023-01-14T00:18:46 Z	chezpotato	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	1000 ms	24468 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;

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

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

}

Subtask #1

95.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	2972 KB	Output is correct
2	Correct	82 ms	2928 KB	Output is correct
3	Correct	86 ms	3092 KB	Output is correct
4	Correct	86 ms	2888 KB	Output is correct
5	Correct	78 ms	2980 KB	Output is correct
6	Correct	78 ms	2876 KB	Output is correct
7	Correct	78 ms	2948 KB	Output is correct
8	Correct	77 ms	3060 KB	Output is correct
9	Correct	216 ms	5620 KB	Output is correct
10	Correct	211 ms	5696 KB	Output is correct
11	Correct	92 ms	2576 KB	Output is correct
12	Correct	189 ms	5056 KB	Output is correct
13	Correct	292 ms	8408 KB	Output is correct
14	Correct	449 ms	11212 KB	Output is correct
15	Correct	507 ms	11368 KB	Output is correct
16	Correct	647 ms	14284 KB	Output is correct
17	Correct	758 ms	19612 KB	Output is correct
18	Correct	881 ms	20008 KB	Output is correct
19	Execution timed out	1093 ms	24468 KB	Time limit exceeded
20	Correct	787 ms	19764 KB	Output is correct