Submission #1235524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235524		henrii	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	175 ms	13624 KiB

jobs

#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 || (curr_day == i + d && job_requests > 0)) 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;
}

• Subtask 1: 55 / 100