oj.uz

답안 #1015869

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1015869 2024-07-06T23:38:35 Z rcll Job Scheduling (CEOI12_jobs) C++17
100 / 100
 378 ms 26504 KB 
#include <bits/stdc++.h>
using namespace std;

int n,d,m;

pair<bool,vector<vector<int>>> check(const vector<pair<int,int>> &jobs,int count) {
    vector<vector<int>> schedule(n);
    int request_num=0;
    for (int day=1; day<=n; day++) {
        for (int j=0; j<count; j++) {
            if (jobs[request_num].first>day) {
                break;
            }
            if (jobs[request_num].first+d>=day) {
                schedule[day-1].push_back(jobs[request_num++].second);
            }
            else {
                return make_pair(false,schedule);
            }
            if (m==request_num) {
                return make_pair(true,schedule);
            }
        }
    }
    return make_pair(false,schedule);
}

int main() {
    cin >> n >> d >> m;
    vector<pair<int,int>> jobs(m);
    for (int i = 0; i < m; i++) {
        int day;
        cin >> day;
        jobs[i] = make_pair(day,i+1);
    }
    sort(jobs.begin(),jobs.end());

    vector<vector<int>> results;
    int lower=1,upper=m;
    while (lower<upper) {
        int machines=(lower+upper)/2;
        pair<bool,vector<vector<int>>> result =check(jobs,machines);
        if (result.first) {
            upper=machines;
            results=result.second;
        }
        else
            lower=machines+1;
    }

    cout << lower << endl;
    for (int i=0; i<n; i++) {
        for (int &idx:results[i]) cout << idx << " ";
        cout << 0 << endl;
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3180 KB Output is correct
2 Correct 36 ms 3096 KB Output is correct
3 Correct 38 ms 3096 KB Output is correct
4 Correct 39 ms 3088 KB Output is correct
5 Correct 45 ms 3096 KB Output is correct
6 Correct 37 ms 3092 KB Output is correct
7 Correct 34 ms 3096 KB Output is correct
8 Correct 35 ms 3096 KB Output is correct
9 Correct 189 ms 9804 KB Output is correct
10 Correct 178 ms 9820 KB Output is correct
11 Correct 33 ms 2984 KB Output is correct
12 Correct 59 ms 4952 KB Output is correct
13 Correct 91 ms 8672 KB Output is correct
14 Correct 163 ms 10924 KB Output is correct
15 Correct 150 ms 11112 KB Output is correct
16 Correct 236 ms 16188 KB Output is correct
17 Correct 250 ms 18740 KB Output is correct
18 Correct 265 ms 23184 KB Output is correct
19 Correct 378 ms 26504 KB Output is correct
20 Correct 264 ms 18776 KB Output is correct