Submission #567594

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
567594	2022-05-23T19:05:55 Z	TheEccentricDuck	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	314 ms	13748 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	1612 KB	Output is correct
2	Correct	26 ms	1632 KB	Output is correct
3	Correct	27 ms	1656 KB	Output is correct
4	Correct	28 ms	1676 KB	Output is correct
5	Correct	28 ms	1592 KB	Output is correct
6	Correct	29 ms	1596 KB	Output is correct
7	Correct	28 ms	1592 KB	Output is correct
8	Correct	26 ms	1592 KB	Output is correct
9	Correct	31 ms	1824 KB	Output is correct
10	Correct	32 ms	1848 KB	Output is correct
11	Correct	39 ms	1612 KB	Output is correct
12	Correct	67 ms	3136 KB	Output is correct
13	Correct	110 ms	4556 KB	Output is correct
14	Correct	164 ms	6128 KB	Output is correct
15	Correct	172 ms	7536 KB	Output is correct
16	Correct	253 ms	9096 KB	Output is correct
17	Correct	295 ms	10484 KB	Output is correct
18	Correct	277 ms	12056 KB	Output is correct
19	Correct	314 ms	13748 KB	Output is correct
20	Correct	308 ms	10512 KB	Output is correct