Submission #410604

#	Time	Username	Problem	Language	Result	Execution time	Memory
410604		four_specks	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	412 ms	26372 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    struct job
    {
        int day;
        int index;
    };

    int n, d;
    int m;
    cin >> n >> d >> m;

    vector<job> jobs(m);
    for (int j = 0; j < m; j++)
        cin >> jobs[j].day, jobs[j].index = j;
    sort(jobs.begin(), jobs.end(), [](const auto &lhs, const auto &rhs) -> bool
         { return lhs.day < rhs.day; });

    auto valid = [&](const int &w) -> pair<bool, vector<vector<int>>>
    {
        vector<vector<int>> sc(n);
        for (int i = 0, j = 0; i < n && j < m; i++)
        {
            for (int c = w; j < m && c > 0 && jobs[j].day <= i + 1; j++, c--)
            {
                if (i + 1 - jobs[j].day > d)
                    return {0, {}};
                sc[i].push_back(jobs[j].index + 1);
            }
        }

        return {1, sc};
    };

    int ans = m;
    vector<vector<int>> schedule;
    for (int l = 1; l < ans;)
    {
        int mid = (l + ans) / 2;
        if (const auto &[s, v] = valid(mid); s)
        {
            ans = mid;
            schedule = v;
        }
        else
            l = mid + 1;
    }

    cout << ans << '\n';
    for (const auto &ids : schedule)
    {
        for (const auto &id : ids)
            cout << id << ' ';
        cout << 0 << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

• Subtask 1: 100 / 100