Submission #653663

#	Time	Username	Problem	Language	Result	Execution time	Memory
653663		finn__	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	360 ms	26824 KiB

jobs

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

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

    unsigned n, m, d;
    cin >> n >> d >> m;

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

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

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

        queue<pair<int32_t, unsigned>> q;
        bool possible = 1;
        auto it = jobs.begin();
        vector<int32_t> local_schedule;

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

            for (unsigned j = 0; j < mid && !q.empty(); j++)
            {
                if (i - q.front().first > d)
                {
                    possible = 0;
                    break;
                }
                local_schedule.push_back(q.front().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 (int32_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: 'int32_t' {aka 'int'} and 'unsigned int' [-Wsign-compare]
   33 |         for (int32_t i = 1; i <= n && possible; i++)
      |                             ~~^~~~
jobs.cpp:41:36: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int32_t' {aka 'int'} [-Wsign-compare]
   41 |             for (unsigned j = 0; j < mid && !q.empty(); j++)
      |                                  ~~^~~~~
jobs.cpp:43:41: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'unsigned int' [-Wsign-compare]
   43 |                 if (i - q.front().first > d)
      |                     ~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 100 / 100