Submission #479218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479218	2021-10-10T17:27:09 Z	cheeseman	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	980 ms	19980 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	126 ms	4204 KB	Output is correct
2	Correct	116 ms	4168 KB	Output is correct
3	Correct	122 ms	4356 KB	Output is correct
4	Correct	162 ms	4220 KB	Output is correct
5	Correct	117 ms	4192 KB	Output is correct
6	Correct	113 ms	4188 KB	Output is correct
7	Correct	131 ms	4244 KB	Output is correct
8	Correct	113 ms	4176 KB	Output is correct
9	Correct	240 ms	7096 KB	Output is correct
10	Correct	239 ms	7180 KB	Output is correct
11	Correct	77 ms	1904 KB	Output is correct
12	Correct	230 ms	3936 KB	Output is correct
13	Correct	270 ms	6592 KB	Output is correct
14	Correct	442 ms	9416 KB	Output is correct
15	Correct	347 ms	8516 KB	Output is correct
16	Correct	438 ms	11188 KB	Output is correct
17	Correct	609 ms	15700 KB	Output is correct
18	Correct	850 ms	15036 KB	Output is correct
19	Correct	980 ms	19980 KB	Output is correct
20	Correct	605 ms	15864 KB	Output is correct