Submission #483964

#	Time	Username	Problem	Language	Result	Execution time	Memory
483964		tibiCoder	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	1096 ms	34368 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;
    int id;

    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, int nOfDays, bool print) {
    priority_queue<Event, vector<Event>, greater<>> nextFreeMachine;
    for (int i = 0; i < jobs.size(); ++i) {
        nextFreeMachine.push({jobs[i], jobs[i], false, i});
    }
    vector<vector<int>> jobsPerDay;
    if (print) {
        jobsPerDay.resize(nOfDays+1);
    }

    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, event.id});
            if (print) {
                jobsPerDay[event.time].emplace_back(event.id+1);
            }
        }
        else {
            nextFreeMachine.push({event.time+1, event.arrival, false, event.id});
        }
    }
    if (print) {
        for (int i = 1; i < jobsPerDay.size(); ++i) {
            for (int j = 0; j < jobsPerDay[i].size(); ++j) {
                cout << jobsPerDay[i][j] << " ";
            }
            cout << "0\n";
        }
    }
    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];
    }

    int start = 1;
    int end = 1000000;
    int low;
    while (start <= end) {
        int middle = start + (end-start)/2;
        if (isPossibleForMachines(jobs, maxDelay, middle, nOfDays, false)) {
            low = middle;
            end = middle-1;
        }
        else {
            start = middle+1;
        }
    }
    cout << low << '\n';
    isPossibleForMachines(jobs, maxDelay, low, nOfDays, true);



    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool isPossibleForMachines(std::vector<int>&, int, int, int, bool)':
jobs.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < jobs.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
jobs.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int i = 1; i < jobsPerDay.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int j = 0; j < jobsPerDay[i].size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:108:26: warning: 'low' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |     isPossibleForMachines(jobs, maxDelay, low, nOfDays, true);
      |     ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 55 / 100