oj.uz

답안 #650832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650832 2022-10-15T13:42:16 Z borisAngelov Job Scheduling (CEOI12_jobs) C++11
100 / 100
 434 ms 26184 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

int n, m, d;

vector<pair<int, int>> jobs;

pair<bool, vector<vector<int>>> check(int machines) {
    vector<vector<int>> schedule;
    schedule.resize(n + 1);

    int currJob = 0;

    for (int day = 1; day <= n; day++) {
        for (int j = 0; j < machines; j++) {
            if (jobs[currJob].first > day) break;

            if (jobs[currJob].first + d >= day) {
                schedule[day].push_back({jobs[currJob++].second});
            } else {
                return {false, schedule};
            }

            if (currJob == m) {
                return {true, schedule};
            }
        }
    }

    return {false, schedule};
}

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

    cin >> n >> d >> m;

    for (int i = 1; i <= m; i++) {
        int day; cin >> day;
        jobs.push_back({day, i});
    }

    sort(jobs.begin(), jobs.end());

    int l = 1;
    int r = m;

    while (l <= r) {
        int mid = (l + r) / 2;

        if (check(mid).first) r = mid - 1;
        else l = mid + 1;
    }

    cout << l << "\n";

    vector<vector<int>> schedule = check(l).second;

    for (int i = 1; i <= n; i++) schedule[i].push_back(0);

    for (int i = 1; i <= n; i++) {
        cout << schedule[i][0];
        for (int j = 1; j < schedule[i].size(); j++) cout << " " << schedule[i][j];
        cout << "\n";
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int j = 1; j < schedule[i].size(); j++) cout << " " << schedule[i][j];
      |                         ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 3092 KB Output is correct
2 Correct 34 ms 3156 KB Output is correct
3 Correct 34 ms 3080 KB Output is correct
4 Correct 34 ms 3220 KB Output is correct
5 Correct 38 ms 3184 KB Output is correct
6 Correct 33 ms 3148 KB Output is correct
7 Correct 33 ms 3116 KB Output is correct
8 Correct 33 ms 3220 KB Output is correct
9 Correct 91 ms 8072 KB Output is correct
10 Correct 96 ms 8004 KB Output is correct
11 Correct 40 ms 2620 KB Output is correct
12 Correct 77 ms 5092 KB Output is correct
13 Correct 122 ms 7912 KB Output is correct
14 Correct 180 ms 11012 KB Output is correct
15 Correct 204 ms 11656 KB Output is correct
16 Correct 258 ms 15424 KB Output is correct
17 Correct 304 ms 19072 KB Output is correct
18 Correct 323 ms 19884 KB Output is correct
19 Correct 434 ms 26184 KB Output is correct
20 Correct 334 ms 19112 KB Output is correct