Submission #483968

#	Time	Username	Problem	Language	Result	Execution time	Memory
483968		tibiCoder	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	482 ms	25976 KiB

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 (stderr)

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 / 100