Submission #567594

#	Time	Username	Problem	Language	Result	Execution time	Memory
567594		TheEccentricDuck	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	314 ms	13748 KiB

jobs

//======================================================================================================================
// Name        : job_scheduling.cpp
// Author      : Jinchen Li
// Date Created: 5/22/2022
// Description : oj.uz, CEOI 2012 Day 1 Problem 1, Job Scheduling in C++, Ansi-style
//======================================================================================================================

// Directives
#include <algorithm>
#include <iostream>
#include <vector>

// Request Structure
struct request {
    int id = 0;
    int time = 0;
    bool operator < (const request& rhs) const {
        return time < rhs.time;
    }
};

// Function Declarations
bool is_num_able(const int& D, const int& M, const int& machine_num, const std::vector<request>& requests);

// Main
int main() {
    // Accepting Inputs
    int N;
    int D;
    int M;
    std::cin >> N >> D >> M;
    std::vector<request> requests (M);
    for (int x = 1; x <= M; x++) {
        std::cin >> requests[x - 1].time;
        requests[x - 1].id = x;
    }

    // Processing Inputs
    std::sort(requests.begin(), requests.end());
    int low = 1;
    int high = M;
    while (low < high) {
        int cur = low + (high - low) / 2;
        if (is_num_able(D, M, cur, requests)) {
            high = cur;
        }
        else {
            low = cur + 1;
        }
    }

    // Printing Outputs
    int print_ind {};
    std::cout << low << '\n';
    for (int x = 0; x < N; x++) {
        int prev_print_ind = print_ind;
        for (; print_ind < prev_print_ind + low && print_ind < M && requests[print_ind].time <= x + 1; print_ind++) {
            std::cout << requests[print_ind].id << ' ';
        }
        std::cout << "0\n";
    }
}

// Is Amount of Machines Able Function
bool is_num_able(const int& D, const int& M, const int& machine_num, const std::vector<request>& requests) {
    int x = 0;
    int cur_day = 1;
    while (x < M) {
        cur_day = std::max(cur_day, requests[x].time);
        request upper_bound_request = {.id = 0, .time = cur_day};
        auto next_ind = static_cast<int>(std::upper_bound(requests.begin() + x, requests.end(), upper_bound_request) - requests.begin());
        if (cur_day > requests[x].time + D) {
            return false;
        }
        if (next_ind - x > machine_num) {
            next_ind = x + machine_num;
        }
        cur_day++;
        x = next_ind;
    }
    return true;
}

• Subtask 1: 100 / 100