Submission #550360

#	Time	Username	Problem	Language	Result	Execution time	Memory
550360		FromDihPout	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	257 ms	23640 KiB

jobs

/**
 *    author:  FromDihPout
 *    created: 2022-04-17
**/
 
#include <bits/stdc++.h>
using namespace std;

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

    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a.begin(), a.end());

    auto check = [&](int x) {
        int day = 1, cnt = 0;
        for (int i = 0; i < m; i++) {
            if (day < a[i].first || cnt >= x) {
                day = max(day + 1, a[i].first);
                cnt = 0;
            }
            if (day - a[i].first > d) {
                return false;
            }
            cnt += 1;
        }
        return day <= n;
    };

    int l = 1, r = m;
    int machines = r;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            machines = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    int day = 0;
    vector<vector<int>> res;
    for (int i = 0; i < m; i++) {
        while (a[i].first > day || res.back().size() >= machines) {
            res.push_back({});
            day++;
        }
        res.back().push_back(a[i].second);
    }
    while (day < n) {
        res.push_back({});
        day++;
    }

    cout << machines << '\n';
    for (int i = 0; i < n; i++) {
        for (int id : res[i]) {
            cout << id << ' ';
        }
        cout << '0' << '\n';
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:52:54: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         while (a[i].first > day || res.back().size() >= machines) {
      |                                    ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 100 / 100