Submission #1122781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122781		marcus06	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	283 ms	26920 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(N);
    auto isGood = [&](int x) -> bool {
        vector <vector <int>> schedule(N);
        int ptr = 0;
        for (int days = 1; days <= N; ++days) {
            for (int j = 0; j < x; ++j) {
                if (ptr >= M || d[ord[ptr]] > days) break;

                if (d[ord[ptr]] + D >= days) {
                    schedule[days - 1].push_back(ord[ptr++]);
                } else return false;
            }
        }

        ans = schedule;
        schedule.clear();
        return ptr == M;
    };

    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: 100 / 100