제출 #1324054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324054		sh_qaxxorov_571	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	176 ms	17852 KiB

jobs

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

using namespace std;

struct Job {
    int day, id;
};

int N, D, M;
vector<Job> jobs;
vector<int> schedule[100005];

// Berilgan K ta mashina bilan ishlarni bajarish mumkinligini tekshirish
bool check(int K, bool save_schedule) {
    if (save_schedule) {
        for (int i = 1; i <= N; i++) schedule[i].clear();
    }

    queue<Job> q;
    int job_idx = 0;

    for (int day = 1; day <= N; day++) {
        // Shu kuni kelgan ishlarni navbatga qo'shish
        while (job_idx < M && jobs[job_idx].day == day) {
            q.push(jobs[job_idx]);
            job_idx++;
        }

        // K ta mashinada ishlarni bajarish
        for (int m = 0; m < K && !q.empty(); m++) {
            Job current = q.front();
            q.pop();

            // Kechikish cheklovini tekshirish
            if (day > current.day + D) return false;

            if (save_schedule) {
                schedule[day].push_back(current.id);
            }
        }
    }

    return q.empty();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> D >> M;
    for (int i = 0; i < M; i++) {
        int d;
        cin >> d;
        jobs.push_back({d, i + 1});
    }

    // Ishlarni kelgan kuni bo'yicha tartiblaymiz
    sort(jobs.begin(), jobs.end(), [](Job a, Job b) {
        return a.day < b.day;
    });

    // Binary search orqali minimal mashinalar sonini topish
    int low = 1, high = M, ans = M;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid, false)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    // Optimal natija bilan jadvalni qayta hisoblash
    cout << ans << "\n";
    check(ans, true);

    for (int i = 1; i <= N; i++) {
        for (int id : schedule[i]) {
            cout << id << " ";
        }
        cout << "0\n";
    }

    return 0;
}

• Subtask 1: 100 / 100