Submission #483959

#	Time	Username	Problem	Language	Result	Execution time	Memory
483959		tibiCoder	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1097 ms	26688 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;

struct Event {
    int time;
    int arrival;
    bool isEnd;

    bool operator>(const Event& other) const {
        if (time == other.time) {
            if (isEnd == other.isEnd) {
                return arrival > other.arrival;
            }
            return !isEnd && other.isEnd;
        }
        return time > other.time;
    }

};

bool isPossibleForMachines(vector<int>& jobs, int maxDelay, int nOfMachines) {
    priority_queue<Event, vector<Event>, greater<>> nextFreeMachine;
    for (int & job : jobs) {
        nextFreeMachine.push({job, job, false});
    }

    while (!nextFreeMachine.empty()) {
        Event event = nextFreeMachine.top();
        nextFreeMachine.pop();
        while (!nextFreeMachine.empty() && nextFreeMachine.top().isEnd && nextFreeMachine.top().time==event.time) {
            nextFreeMachine.pop();
            ++nOfMachines;
        }
        if (event.isEnd) {
            ++nOfMachines;
            continue;
        }
        if (nOfMachines > 0) {
            --nOfMachines;
            if (event.time-event.arrival > maxDelay) {
                return false;
            }
            nextFreeMachine.push({event.time+1, event.arrival, true});
        }
        else {
            nextFreeMachine.push({event.time+1, event.arrival, false});
        }
    }
    return true;
}


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

    int start = 1;
    int end = 1000000;
    int low;
    while (start <= end) {
        int middle = start + (end-start)/2;
        if (isPossibleForMachines(jobs, maxDelay, middle)) {
            low = middle;
            end = middle-1;
        }
        else {
            start = middle+1;
        }
    }
    cout << low << "\n0";



    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:92:20: warning: 'low' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |     cout << low << "\n0";
      |                    ^~~~~

• Subtask 1: 0 / 100