Submission #483968

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483968	2021-11-01T16:31:50 Z	tibiCoder	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	482 ms	25976 KB

jobs

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <climits>
#include <unordered_map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <bitset>
#include <iomanip>

using namespace std;

pair<bool, vector<vector<int>>> isFeasible(vector<pair<int, int>> &jobs, int nOfDays, int maxDelay, int nOfRequests, int machineCount) {
    vector<vector<int>> schedule(nOfDays);
    int reqNum = 0;
    // we simulate from day 1 until the last day N
    // we move to the next day if all the machines are used or
    // there is no more job requests left on or before this day
    for (int day = 1; day <= nOfDays; 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
            // we can determine that since the vector jobs is sorted
            if (jobs[reqNum].first > day)
                break;
            // if the current date is before the deadline for the job
            // we can add this job to the schedule and move to the next job request
            if (jobs[reqNum].first + maxDelay >= day)
                schedule[day - 1].push_back(jobs[reqNum++].second);
                // otherwise, it is not feasible due to deadline
            else
                return make_pair(false, schedule);

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


int main() {
    int nOfDays, maxDelay, nOfJobRequests;
    cin >> nOfDays >> maxDelay >> nOfJobRequests;
    vector<pair<int, int>> jobs(nOfJobRequests);
    for (int i = 0; i < nOfJobRequests; ++i) {
        cin >> jobs[i].first;
        jobs[i].second = i+1;
    }
    std::sort(jobs.begin(), jobs.end());

    int start = 1;
    int end = 100000;
    int low;
    while (start <= end) {
        int middle = start + (end-start)/2;
        if (isFeasible(jobs, nOfDays, maxDelay, nOfJobRequests, middle).first) {
            low = middle;
            end = middle-1;
        }
        else {
            start = middle+1;
        }
    }
    cout << low << '\n';
    auto result = isFeasible(jobs, nOfDays, maxDelay, nOfJobRequests, low).second;
    for (int i = 0; i < result.size(); i++) {
        for (int &idx : result[i])
            cout << idx << " ";
        cout << 0 << "\n";
    }



    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < result.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
jobs.cpp:77:74: warning: 'low' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     auto result = isFeasible(jobs, nOfDays, maxDelay, nOfJobRequests, low).second;
      |                                                                          ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	2940 KB	Output is correct
2	Correct	41 ms	2928 KB	Output is correct
3	Correct	41 ms	2908 KB	Output is correct
4	Correct	41 ms	2864 KB	Output is correct
5	Correct	41 ms	2920 KB	Output is correct
6	Correct	45 ms	2932 KB	Output is correct
7	Correct	41 ms	2936 KB	Output is correct
8	Correct	40 ms	2896 KB	Output is correct
9	Correct	83 ms	7416 KB	Output is correct
10	Correct	86 ms	7396 KB	Output is correct
11	Correct	48 ms	2616 KB	Output is correct
12	Correct	98 ms	5116 KB	Output is correct
13	Correct	141 ms	7780 KB	Output is correct
14	Correct	225 ms	10912 KB	Output is correct
15	Correct	242 ms	11544 KB	Output is correct
16	Correct	319 ms	14720 KB	Output is correct
17	Correct	386 ms	19048 KB	Output is correct
18	Correct	423 ms	19704 KB	Output is correct
19	Correct	482 ms	25976 KB	Output is correct
20	Correct	385 ms	18972 KB	Output is correct