Submission #653663

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
653663	2022-10-27T15:10:45 Z	finn__	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	360 ms	26824 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	3260 KB	Output is correct
2	Correct	32 ms	3244 KB	Output is correct
3	Correct	33 ms	3280 KB	Output is correct
4	Correct	31 ms	3268 KB	Output is correct
5	Correct	31 ms	3280 KB	Output is correct
6	Correct	32 ms	3264 KB	Output is correct
7	Correct	31 ms	3280 KB	Output is correct
8	Correct	32 ms	3248 KB	Output is correct
9	Correct	45 ms	5020 KB	Output is correct
10	Correct	46 ms	5024 KB	Output is correct
11	Correct	36 ms	3260 KB	Output is correct
12	Correct	77 ms	6332 KB	Output is correct
13	Correct	112 ms	10032 KB	Output is correct
14	Correct	151 ms	12512 KB	Output is correct
15	Correct	187 ms	13536 KB	Output is correct
16	Correct	225 ms	20040 KB	Output is correct
17	Correct	262 ms	22400 KB	Output is correct
18	Correct	310 ms	26708 KB	Output is correct
19	Correct	360 ms	26824 KB	Output is correct
20	Correct	272 ms	22344 KB	Output is correct