Submission #653657

#	Time	Username	Problem	Language	Result	Execution time	Memory
653657		finn__	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1084 ms	26104 KiB

jobs

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

int main()
{
    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 a = 0, 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();
        schedule.clear();

        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;
                }
                schedule.push_back(q.top().second);
                q.pop();
            }

            schedule.push_back(0);
        }

        if (possible)
            b = mid;
        else
            a = mid + 1;
    }

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

Compilation message (stderr)

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

• Subtask 1: 0 / 100