Submission #479218

#	Time	Username	Problem	Language	Result	Execution time	Memory
479218		cheeseman	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	980 ms	19980 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

long long n, m, d;

bool works(long long machines, vector<vector<int>> &reqs)
{
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for (int i = 0; i < n; i++)
    {
        for (unsigned int j = 0; j < reqs[i].size(); j++)
        {
            pq.push(i + d);
        }
        for (int j = 0; j < machines; j++)
        {
            if (pq.empty())
            {
                break;
            }
            if (pq.top() < i)
            {
                return false;
            }
            pq.pop();
        }
    }
    return true;
}
int main()
{
    cin >> n >> d >> m;
    vector<vector<int>> reqs(n);
    int day;
    for (int i = 0; i < m; i++)
    {
        cin >> day;
        reqs[day - 1].push_back(i);
    }

    long long l = 1, r = m;
    long long best = INT_MAX;
    while (l <= r)
    {
        long long mid = (l + r) / 2;
        if (works(mid, reqs))
        {
            r = mid - 1;
            best = mid;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout << best << endl;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        pq;
    vector<vector<int>> sol(n);
    for (int i = 0; i < n; i++)
    {
        for (int j : reqs[i])
        {
            pq.push(make_pair(i + d, j));
        }
        for (int j = 0; j < best; j++)
        {
            if (pq.empty())
            {
                break;
            }
            sol[i].push_back(pq.top().second + 1);
            pq.pop();
        }
    }

    for (auto i : sol)
    {
        for (int req : i)
        {
            cout << req << ' ';
        }
        cout << 0 << endl;
    }
}

• Subtask 1: 100 / 100