Submission #1235522

#TimeUsernameProblemLanguageResultExecution timeMemory
1235522henriiJob Scheduling (CEOI12_jobs)C++17
15 / 100
170 ms13624 KiB
#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define pii pair<int, int>
#define ll long long

int main()
{

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

    vector<vi> adj(n + 1);
    for (int i = 1; i < m + 1; ++i)
    {
        int day;
        cin >> day;

        adj[day].push_back(i);
    }

    auto good = [&](int machines)
    {
        int curr_day = 0;
        int job_requests = 0;
        for (int i = 1; i < n + 1; ++i)
        {
            job_requests += adj[i].size();
            curr_day += job_requests / machines;
            job_requests %= machines;

            if (curr_day > i + d) return false;
        }

        return true;
    };

    int lo = 1, hi = m;
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        if (good(mid))
        {
            hi = mid;
        }
        else
        {
            lo = mid + 1;
        }
    }

    cout << lo << endl;

    queue<int> q;
    for (int i = 1; i < n + 1; ++i)
    {
        for (int job: adj[i]) q.push(job);
        int counter = 0;
        while (counter < lo && !q.empty())
        {
            cout << q.front() << " ";
            q.pop();
            counter++;
        }

        cout << "0\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...