Submission #1122772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122772		marcus06	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	283 ms	24100 KiB

jobs

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

//replace with your directory
#ifdef LOCAL
#include <C:/Coding/CP/templates/content/debug/debug.h>
#else
#define debug(...) 
#endif
 
void solve() {
    int N, D, M;
    cin >> N >> D >> M;
    vector <int> d(M);
    for (int i = 0; i < M; ++i) {
        cin >> d[i];
    }

    vector <int> ord(M);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){
        return d[i] < d[j];
    });

    vector <vector <int>> ans;
    auto isGood = [&](int x) -> bool {
        vector <vector <int>> schedule;
        for (int i = 0; i < M; ++i) {
            if(schedule.empty() || (int) schedule.back().size() == x) {
                schedule.emplace_back();
            }
            schedule.back().emplace_back(ord[i]);
        }

        for (int i = 0; i < (int) schedule.size(); ++i) {
            for (int &v: schedule[i]) {
                if (i - D >= d[v]) return false;
            }
        }

        ans.clear();
        ans = schedule;
        return true;
    };

    int l = 0, r = M;
    while (r - l > 1) {
        int m = (l + r) / 2;

        if (isGood(m)) r = m;
        else l = m;
    }

    cout << r << '\n';
    for (int i = 0; i < N; ++i) {
        if (i < (int) ans.size()) {
            for (const int &v: ans[i]) cout << v + 1 << ' ';
        }
        cout << "0\n";
    }
}
 
int main() {
    std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    auto begin = std::chrono::high_resolution_clock::now();
#endif
 
    int tt = 1;
    while (tt--) {
        solve();
    }
 
#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
 
    return 0;
}

• Subtask 1: 55 / 100