제출 #925518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925518		allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	279 ms	26496 KiB

jobs

#include <iostream>
#include <vector>

bool run(std::vector<int> a, int d, int x, std::vector<std::vector<int>>& answer, std::vector<std::vector<int>> ids) {
    int i = a.size() - d - 1;
    for (int j = a.size() - 1; i >= 0 && j >= 0; --j) {
        //std::cout << i << ' ' << j << '\n';
        int v = std::min(a[i], x);
        a[i] -= v;
        
        while (v > 0) {
            //std::cout << "To " << j << " add " << ids[i].back() << '\n';
            answer[j].push_back(ids[i].back());
            ids[i].pop_back();
            --v;
        }
        if (i == j && a[i] != 0) return false;
        if (a[i] == 0) --i;
        if (a[i] < 0) break;
    }

    return true;
}

int main() {
    int n, d, m;
    std::cin >> n >> d >> m;
    std::vector<int> a(n + 1, 0);
    std::vector<std::vector<int>> ids(n + 1, std::vector<int>());

    for (int i = 0; i < m; ++i) {
        int tmp; std::cin >> tmp;
        a[tmp]++;
        ids[tmp].push_back(i + 1);
    }

    int l = 0;
    int r = n;
    std::vector<std::vector<int>> answer;
    // (l, r]
    while (l + 1 < r) {
        answer = std::vector<std::vector<int>>(n + 1, std::vector<int>());
        int m = (l + r) / 2;
        if (run(a, d, m, answer, ids)) {
            r = m;
        } else {
            l = m;
        }
    }

    answer = std::vector<std::vector<int>>(n + 1, std::vector<int>());
    run(a, d, r, answer, ids);
    std::cout << r << '\n';

    for (int i = 1; i <= n; ++i) {
        for (size_t j = 0; j < answer[i].size(); ++j) {
            std::cout << answer[i][j] << ' ';
        }
        std::cout << "0\n";
    }
}

• Subtask 1: 0 / 100