Submission #653660

#	Time	Username	Problem	Language	Result	Execution time	Memory
653660		finn__	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	1086 ms	40984 KiB

jobs

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

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    size_t n, m, d;
    cin >> n >> d >> m;

    vector<pair<int64_t, size_t>> jobs(m);
    for (size_t i = 0; i < m; i++)
    {
        cin >> jobs[i].first;
        jobs[i].second = i + 1;
    }

    sort(jobs.begin(), jobs.end());
    vector<int64_t> schedule;
    int64_t min_machines = m;

    int64_t a = 1, b = m;
    while (a < b)
    {
        int64_t mid = (a + b) / 2;

        priority_queue<pair<int64_t, size_t>, vector<pair<int64_t, size_t>>, greater<pair<int64_t, size_t>>> q;
        bool possible = 1;
        auto it = jobs.begin();
        vector<int64_t> local_schedule;

        for (int64_t i = 1; i <= n && possible; i++)
        {
            while (it != jobs.end() && it->first == i)
            {
                q.push(*it);
                it++;
            }

            for (size_t j = 0; j < mid && !q.empty(); j++)
            {
                if (i - q.top().first > d)
                {
                    possible = 0;
                    break;
                }
                local_schedule.push_back(q.top().second);
                q.pop();
            }

            local_schedule.push_back(0);
        }

        if (possible)
        {
            b = mid;
            if (mid < min_machines)
            {
                min_machines = mid;
                swap(local_schedule, schedule);
            }
        }
        else
            a = mid + 1;
    }

    cout << a << '\n';
    for (int64_t x : schedule)
    {
        cout << x;
        if (!x)
            cout << '\n';
        else
            cout << ' ';
    }
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:33:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int64_t i = 1; i <= n && possible; i++)
      |                             ~~^~~~
jobs.cpp:41:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   41 |             for (size_t j = 0; j < mid && !q.empty(); j++)
      |                                ~~^~~~~
jobs.cpp:43:39: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 if (i - q.top().first > d)
      |                     ~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 80 / 100