Submission #1231620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231620		siryellsalot	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	364 ms	20648 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <cmath>

using std::vector, std::pair;

bool sort_by_second(const pair<int, int>& first, const pair<int, int>& second) {
    if (first.second == second.second) {
        return first.first < second.first;
    }
    return first.second < second.second;
}

bool simulate(const vector<pair<int,int>>& jobs, int& days, int& max_delay, uint64_t& guess, vector<pair<int,int>>& out) {
    out.clear();
    auto job_index = 0;
    for (auto cur_day = 1; cur_day <= days; cur_day++) {
        for (auto i = 0; i < guess; i++) {
            if (job_index >= jobs.size()) {
                return true;
            }
            const auto& [jobid, day] = jobs[job_index];
            int diff = cur_day - day;
            if (diff < 0) {
                break;
            }
            if (diff > max_delay) {
                return false;
            }
            out.push_back(pair(jobid, cur_day));
            job_index++;
        }
    }
    return false;
}


int main() {
    int days, max_delay, num_jobs;
    std::cin >> days >> max_delay >> num_jobs;
    vector<pair<int, int>> jobs(num_jobs);

    for (auto i = 0; i < num_jobs; i++) {
        jobs[i].first = i;
        std::cin >> jobs[i].second;
    }

    std::sort(jobs.begin(), jobs.end(), sort_by_second);
    uint64_t upper_bound = num_jobs;
    uint64_t lower_bound = 0;
    uint64_t guess = num_jobs/days;
    vector<pair<int,int>> out(num_jobs);
    while (upper_bound != lower_bound) {
        out.clear();
        if (simulate(jobs, days, max_delay, guess, out)) {
            upper_bound = guess;
        } else {
            lower_bound = guess + 1;
        }
        guess = lower_bound + std::floor((upper_bound - lower_bound) / 2.0);
    }

    std::cout << upper_bound << "\n";
    int lastday = 1;
    for (auto job: out) {
        if (job.second != lastday) {
            std::cout << "0\n";
            lastday = job.second;
        }
        std::cout << job.first + 1 << " ";

    }
    std::cout << "0\n";
    std::cout << "0";
}

• Subtask 1: 0 / 100