Submission #410603

#	Time	Username	Problem	Language	Result	Execution time	Memory
410603		four_specks	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	483 ms	29816 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, d;
    int m;
    cin >> n >> d >> m;

    vector<pair<int, int>> jobs(m);
    for (int j = 0; j < m; j++)
        cin >> jobs[j].first, jobs[j].second = j;
    sort(jobs.begin(), jobs.end());

    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].first <= i + 1; c--)
            {
                if (i + 1 - jobs[j].first > d)
                    return {0, {}};
                else
                {
                    sc[i].push_back(jobs[j].second + 1);
                    j++;
                }
            }
        }

        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