제출 #1088597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1088597		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	297 ms	26960 KiB

jobs

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

using namespace std;

int main() {
    int n, d, m;
    cin >> n >> d >> m;

    vector<vector<int>> tarefas(n + 1);

    vector<int> entrada_tarefas(m);
    for (int i = 0; i < m; ++i) {
        cin >> entrada_tarefas[i];
    }

    for (int i = 0; i < m; ++i) {
        tarefas[entrada_tarefas[i]].push_back(i + 1);
    }

    int l = 1, r = m;
    while (l <= r) {
        int meio = (l + r) / 2;
        bool valido = true;
        int pos_dia = 1;
        int qtd = 0;

        for (int i = 1; i <= n; ++i) {
            int val = tarefas[i].size();
            if (pos_dia < i) {
                pos_dia = i;
                qtd = 0;
            }
            while (val > 0) {
                if (pos_dia - i > d) {
                    valido = false;
                    break;
                }
                --val;
                ++qtd;
                if (qtd == meio) {
                    qtd = 0;
                    ++pos_dia;
                }
            }
            if (!valido) {
                break;
            }
        }

        if (valido) {
            r = meio - 1;
        } else {
            l = meio + 1;
        }
    }

    cout << l << endl;

    vector<vector<int>> resp(n + 1);

    int pos_dia = 1;
    int qtd = 0;
    for (int i = 1; i <= n; ++i) {
        if (pos_dia < i) {
            pos_dia = i;
            qtd = 0;
        }
        while (!tarefas[i].empty()) {
            ++qtd;
            resp[pos_dia].push_back(tarefas[i].back());
            tarefas[i].pop_back();
            if (qtd == l) {
                qtd = 0;
                ++pos_dia;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (size_t j = 0; j < resp[i].size(); ++j) {
            cout << resp[i][j] << " ";
        }
        cout << "0" << endl;
    }

    return 0;
}

• Subtask 1: 100 / 100