Submission #1160673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160673		abdulaziz707	Job Scheduling (CEOI12_jobs)	C++20	Compilation error	0 ms	0 KiB

jobs

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct Request {
    int requestNumber;
    int receivedDay;
    int processedDay;
    Request(int rn, int rd) : requestNumber(rn), receivedDay(rd), processedDay(0) {}
};

struct daySchedule {
    int dayNumber;
    int requestCount;
    daySchedule(int dn, int rc) : dayNumber(dn), requestCount(rc) {}
};

struct CompareDaySchedule {
    bool operator()(const daySchedule& a, const daySchedule& b) const {
        if (a.requestCount != b.requestCount) {
            return a.requestCount > b.requestCount; // Min heap by request count
        }
        return a.dayNumber > b.dayNumber; // Then by day number
    }
};

int main() {
    ios_base::sync_with_stdio(false); // Fast I/O
    cin.tie(NULL);

    int n, d, m;
    cin >> n >> d >> m;

    vector<Request> requests(m);
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        requests[i] = Request(i+1, x); // Store with request number starting from 1
    }

    // Sort by received day for processing
    sort(requests.begin(), requests.end(), [](const Request& a, const Request& b) {
        return a.receivedDay < b.receivedDay;
    });

    // Initialize priority queue with days 1 to d, count 0
    priority_queue<daySchedule, vector<daySchedule>, CompareDaySchedule> pq;
    for(int i = 1; i <= d; i++) {
        pq.push(daySchedule(i, 0));
    }

    int pos = 0;
    // Schedule requests day by day
    for(int day = 1; day <= n && pos < m; day++) {
        pq.push(daySchedule(day + d, 0)); // Add new day for future processing
        if (day < requests[pos].receivedDay) {
            continue; // Skip if no requests yet
        }
        // Process all requests received on this day
        while(pos < m && requests[pos].receivedDay == day) {
            // Remove days earlier than current day
            while(!pq.empty() && pq.top().dayNumber < day) {
                pq.pop();
            }
            daySchedule schedule = pq.top();
            pq.pop();
            schedule.requestCount++; // Increment count for chosen day
            requests[pos].processedDay = schedule.dayNumber; // Assign processing day
            pq.push(schedule); // Put back updated schedule
            pos++;
        }
    }

    // Sort by processed day to find max concurrent
    sort(requests.begin(), requests.end(), [](const Request& a, const Request& b) {
        return a.processedDay < b.processedDay;
    });

    // Find minimum machines (max requests on any day)
    int minimumMachines = 0;
    int currentDay = requests[0].processedDay;
    int count = 0;
    for(int i = 0; i < m; i++) {
        if(requests[i].processedDay == currentDay) {
            count++;
        } else {
            if(count > minimumMachines) {
                minimumMachines = count;
            }
            currentDay = requests[i].processedDay;
            count = 1;
        }
    }
    if(count > minimumMachines) {
        minimumMachines = count;
    }
    cout << minimumMachines << endl;

    // Print schedule for each day from 1 to n
    pos = 0; // Reset for printing
    for(int day = 1; day <= n; day++) {
        while(pos < m && requests[pos].processedDay == day) {
            cout << requests[pos].requestNumber << " ";
            pos++;
        }
        cout << 0 << endl;
    }

    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/11/bits/stl_iterator.h:85,
                 from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from jobs.cpp:1:
/usr/include/c++/11/bits/stl_construct.h: In instantiation of 'constexpr void std::_Construct(_Tp*, _Args&& ...) [with _Tp = Request; _Args = {}]':
/usr/include/c++/11/bits/stl_uninitialized.h:579:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Request*; _Size = long unsigned int; bool _TrivialValueType = false]'
/usr/include/c++/11/bits/stl_uninitialized.h:640:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Request*; _Size = long unsigned int]'
/usr/include/c++/11/bits/stl_uninitialized.h:704:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&) [with _ForwardIterator = Request*; _Size = long unsigned int; _Tp = Request]'
/usr/include/c++/11/bits/stl_vector.h:1606:36:   required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = Request; _Alloc = std::allocator<Request>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
/usr/include/c++/11/bits/stl_vector.h:512:9:   required from 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = Request; _Alloc = std::allocator<Request>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<Request>]'
jobs.cpp:37:31:   required from here
/usr/include/c++/11/bits/stl_construct.h:115:28: error: no matching function for call to 'construct_at(Request*&)'
  115 |           std::construct_at(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/stl_construct.h:94:5: note: candidate: 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...)'
   94 |     construct_at(_Tp* __location, _Args&&... __args)
      |     ^~~~~~~~~~~~
/usr/include/c++/11/bits/stl_construct.h:94:5: note:   template argument deduction/substitution failed:
/usr/include/c++/11/bits/stl_construct.h: In substitution of 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = Request; _Args = {}]':
/usr/include/c++/11/bits/stl_construct.h:115:21:   required from 'constexpr void std::_Construct(_Tp*, _Args&& ...) [with _Tp = Request; _Args = {}]'
/usr/include/c++/11/bits/stl_uninitialized.h:579:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Request*; _Size = long unsigned int; bool _TrivialValueType = false]'
/usr/include/c++/11/bits/stl_uninitialized.h:640:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Request*; _Size = long unsigned int]'
/usr/include/c++/11/bits/stl_uninitialized.h:704:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&) [with _ForwardIterator = Request*; _Size = long unsigned int; _Tp = Request]'
/usr/include/c++/11/bits/stl_vector.h:1606:36:   required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = Request; _Alloc = std::allocator<Request>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
/usr/include/c++/11/bits/stl_vector.h:512:9:   required from 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = Request; _Alloc = std::allocator<Request>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<Request>]'
jobs.cpp:37:31:   required from here
/usr/include/c++/11/bits/stl_construct.h:96:17: error: no matching function for call to 'Request::Request()'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:12:5: note: candidate: 'Request::Request(int, int)'
   12 |     Request(int rn, int rd) : requestNumber(rn), receivedDay(rd), processedDay(0) {}
      |     ^~~~~~~
jobs.cpp:12:5: note:   candidate expects 2 arguments, 0 provided
jobs.cpp:8:8: note: candidate: 'constexpr Request::Request(const Request&)'
    8 | struct Request {
      |        ^~~~~~~
jobs.cpp:8:8: note:   candidate expects 1 argument, 0 provided
jobs.cpp:8:8: note: candidate: 'constexpr Request::Request(Request&&)'
jobs.cpp:8:8: note:   candidate expects 1 argument, 0 provided
In file included from /usr/include/c++/11/bits/stl_iterator.h:85,
                 from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from jobs.cpp:1:
/usr/include/c++/11/bits/stl_construct.h: In instantiation of 'constexpr void std::_Construct(_Tp*, _Args&& ...) [with _Tp = Request; _Args = {}]':
/usr/include/c++/11/bits/stl_uninitialized.h:579:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Request*; _Size = long unsigned int; bool _TrivialValueType = false]'
/usr/include/c++/11/bits/stl_uninitialized.h:640:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Request*; _Size = long unsigned int]'
/usr/include/c++/11/bits/stl_uninitialized.h:704:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&) [with _ForwardIterator = Request*; _Size = long unsigned int; _Tp = Request]'
/usr/include/c++/11/bits/stl_vector.h:1606:36:   required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = Request; _Alloc = std::allocator<Request>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
/usr/include/c++/11/bits/stl_vector.h:512:9:   required from 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = Request; _Alloc = std::allocator<Request>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<Request>]'
jobs.cpp:37:31:   required from here
/usr/include/c++/11/bits/stl_construct.h:119:7: error: no matching function for call to 'Request::Request()'
  119 |       ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:12:5: note: candidate: 'Request::Request(int, int)'
   12 |     Request(int rn, int rd) : requestNumber(rn), receivedDay(rd), processedDay(0) {}
      |     ^~~~~~~
jobs.cpp:12:5: note:   candidate expects 2 arguments, 0 provided
jobs.cpp:8:8: note: candidate: 'constexpr Request::Request(const Request&)'
    8 | struct Request {
      |        ^~~~~~~
jobs.cpp:8:8: note:   candidate expects 1 argument, 0 provided
jobs.cpp:8:8: note: candidate: 'constexpr Request::Request(Request&&)'
jobs.cpp:8:8: note:   candidate expects 1 argument, 0 provided