제출 #1312261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312261		anass.b	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	270 ms	53908 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

/*
 We check whether all jobs can be scheduled with m machines
 such that each job with release day job can be done within
 [job, job + d].
*/
bool can_schedule(const vector<pair<ull,int>>& jobs, ull d, ull m) {
    ull day = 0;
    ull used = 0;

    for (auto &[job, _] : jobs) {
        // Move forward in time if needed
        while (day < job) {
            day++;
            used = 0;
        }

        if (day <= job + d) {
            used++;
            if (used == m) {
                day++;
                used = 0;
            }
        } else {
            return false;
        }
    }
    return true;
}

void solve(vector<pair<ull,int>> jobs, ull n, ull d) {
    ull left = 1;
    ull right = jobs.size();

    // Check if 1 machine is enough
    if (can_schedule(jobs, d, 1)) {
        right = 1;
    } else {
        // Binary search for minimal m
        while (left < right - 1) {
            ull mid = left + (right - left) / 2;
            if (can_schedule(jobs, d, mid))
                right = mid;
            else
                left = mid;
        }
    }

    // Build the actual schedule
    map<int, vector<int>> schedule;
    ull day = 1;

    for (auto &[job, idx] : jobs) {
        while (day < job) day++;

        schedule[day].push_back(idx + 1);

        if (schedule[day].size() == right)
            day++;
    }

    // Output
    cout << right << "\n";
    for (ull i = 1; i <= n; i++) {
        for (int v : schedule[i])
            cout << v << " ";
        cout << 0 << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ull n, d, m;
    cin >> n >> d >> m;

    vector<ull> input(m);
    for (ull i = 0; i < m; i++)
        cin >> input[i];

    vector<pair<ull,int>> jobs;
    for (int i = 0; i < (int)m; i++)
        jobs.push_back({input[i], i});

    sort(jobs.begin(), jobs.end());

    solve(jobs, n, d);
    return 0;
}

• Subtask 1: 80 / 100