제출 #1312014

#제출 시각아이디문제언어결과실행 시간메모리
1312014quacksireJob Scheduling (CEOI12_jobs)C++20
55 / 100
126 ms13972 KiB
#include <bits/stdc++.h>
using namespace std;

struct Job {
    int pos;
    int index;
    Job(int p, int i) : pos(p), index(i) {}
    bool operator<(const Job &other) const {
        return pos < other.pos;
    }
};

bool work(int num, int d, vector<Job> &array) {
    int m = array.size();
    int batches = (m + num - 1) / num;

    for (int i = 0; i < batches; i++) {
        int start = i * num;
        int end = min(start + num, m);

        for (int j = start; j < end; j++) {
            if (array[j].pos + d < i)
                return false;
        }
    }
    return true;
}

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

    int n, d, m;
    cin >> n >> d >> m;

    vector<Job> array;
    for (int i = 0; i < m; i++) {
        int p;
        cin >> p;
        array.emplace_back(p - 1, i + 1);
    }

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

    int l = 1, r = m;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (work(mid, d, array))
            r = mid - 1;
        else
            l = mid + 1;
    }

    cout << l << "\n";

    int batches = (m + l - 1) / l;
    int day = 0;
    for (int i = 0; i < batches; i++) {
        int start = i * l;
        int end = min(start + l, m);
        for (int j = start; j < end; j++)
            cout << array[j].index << " ";
        cout << "0\n";
        day++;
    }

    while (day < n) {
        cout << "0\n";
        day++;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...