oj.uz

Submission #658649

# Submission time Handle Problem Language Result Execution time Memory
658649 2022-11-14T03:55:50 Z stephenc Job Scheduling (CEOI12_jobs) C++17
100 / 100
 423 ms 26404 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using pi = pair<int,int>;
using vi = vector<int>;

int n, m, d;

pair<bool, vector<vi>> isFeasible(vector<pair<int,int>>& jobs, int machineCount) {
    vector<vi> schedule(n);
    int reqNum=0;
    for (int day=1; day<=n; ++day) {
        for (int j=0; j<machineCount; ++j) {
            if (jobs[reqNum].first>day) break;
            if (jobs[reqNum].first+d>=day) {
                schedule[day-1].push_back(jobs[reqNum++].second);
            } else {
                return make_pair(false, schedule);
            }

            if (reqNum==m) {
                return make_pair(true, schedule);
            }
        }
    }
    return make_pair(false, schedule);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>d>>m;
    vector<pi> jobs(m);
    for (int i=0; i<m; ++i) {
        int day;
        cin>>day;
        jobs[i]={day, i+1};
    }
    sort(begin(jobs), end(jobs));
    vector<vi> result;
    int l=1, r=m;
    while (l<r) {
        int machineNum=l+(r-l)/2;
        pair<bool, vector<vi>> curResult = isFeasible(jobs, machineNum);
        if (curResult.first) {
            r=machineNum;
            result=curResult.second;
        } else {
            l=machineNum+1;
        }
    }
    cout<<l<<"\n";
    for (int i=0; i<n; ++i) {
        for (int& idx : result[i]) {
            cout<<idx<<" ";
        }
        cout<<0<<"\n";
    }
}

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2968 KB Output is correct
2 Correct 31 ms 3012 KB Output is correct
3 Correct 28 ms 2992 KB Output is correct
4 Correct 29 ms 3056 KB Output is correct
5 Correct 30 ms 3084 KB Output is correct
6 Correct 32 ms 2968 KB Output is correct
7 Correct 30 ms 3016 KB Output is correct
8 Correct 29 ms 2968 KB Output is correct
9 Correct 75 ms 9660 KB Output is correct
10 Correct 73 ms 9732 KB Output is correct
11 Correct 40 ms 2692 KB Output is correct
12 Correct 73 ms 4960 KB Output is correct
13 Correct 136 ms 8568 KB Output is correct
14 Correct 179 ms 10844 KB Output is correct
15 Correct 190 ms 10988 KB Output is correct
16 Correct 308 ms 16120 KB Output is correct
17 Correct 302 ms 18932 KB Output is correct
18 Correct 310 ms 23212 KB Output is correct
19 Correct 423 ms 26404 KB Output is correct
20 Correct 291 ms 18716 KB Output is correct