Submission #448807

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448807	2021-08-01T18:14:00 Z	chuangsheep	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	480 ms	26880 KB

jobs

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

#define all(x) begin(x), end(x)
#define mp make_pair

using pi = pair<int, int>;
using vi = vector<int>;

// test if it is possible to finish the jobs using given # of machines
// return: first: possible or not, second: if possible, the schedule for the jobs
pair<bool, vector<vi>> isFeasible(const vector<pi> &jobs, int N, int D, int machineCount)
{
    vector<vi> res(N);
    int reqNum = 0;
    for (int day = 1; day <= N; day++)
    {
        for (int j = 0; j < machineCount; j++)
        {
            // if all jobs before and on this day are finished,
            // we can go to the next day, even if there are usable machines left
            if (jobs.at(reqNum).first > day)
                break;
            // if the current date is before the deadline for the job
            if (jobs.at(reqNum).first + D >= day)
                res[day - 1].push_back(jobs.at(reqNum++).second);
            // otherwise, it is not feasible due to deadline
            else
                return mp(false, res);

            // if we have processed all the requests, we have found a feasible sol
            if (reqNum == jobs.size())
                return mp(true, res);
        }
    }
    // if not all the requests can be processed within the given N days,
    // then it is not feasible
    return mp(false, res);
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);

    int N, D, M;
    cin >> N >> D >> M;
    vector<pi> jobs(M);
    for (int i = 0; i < M; i++)
    {
        int day;
        cin >> day;
        // first: request date, second: index [1..M]
        jobs[i] = mp(day, i + 1);
    }
    sort(all(jobs));

    vector<vi> result;
    // binary search on the number of machines
    int l = 1, r = M / D + 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        pair<bool, vector<vi>> cur = isFeasible(jobs, N, D, mid);
        if (cur.first)
        {
            r = mid;
            result = cur.second;
        }
        else
            l = mid + 1;
    }

    cout << l << "\n";
    for (int i = 0; i < N; i++)
    {
        for (int &idx : result[i])
            cout << idx << " ";
        cout << 0 << "\n";
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'std::pair<bool, std::vector<std::vector<int> > > isFeasible(const std::vector<std::pair<int, int> >&, int, int, int)':
jobs.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if (reqNum == jobs.size())
      |                 ~~~~~~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	3576 KB	Output is correct
2	Correct	38 ms	3468 KB	Output is correct
3	Correct	39 ms	3360 KB	Output is correct
4	Correct	39 ms	3400 KB	Output is correct
5	Correct	39 ms	3296 KB	Output is correct
6	Correct	38 ms	3452 KB	Output is correct
7	Correct	40 ms	3500 KB	Output is correct
8	Correct	38 ms	3388 KB	Output is correct
9	Correct	95 ms	9884 KB	Output is correct
10	Correct	94 ms	9920 KB	Output is correct
11	Correct	44 ms	3524 KB	Output is correct
12	Correct	80 ms	5496 KB	Output is correct
13	Correct	123 ms	9060 KB	Output is correct
14	Correct	178 ms	11340 KB	Output is correct
15	Correct	241 ms	11492 KB	Output is correct
16	Correct	309 ms	18104 KB	Output is correct
17	Correct	382 ms	19084 KB	Output is correct
18	Correct	344 ms	18980 KB	Output is correct
19	Correct	480 ms	26880 KB	Output is correct
20	Correct	329 ms	19144 KB	Output is correct