Submission #648316

#	Time	Username	Problem	Language	Result	Execution time	Memory
648316		DarkLightningLord	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	711 ms	27636 KiB

jobs

#include <algorithm>
#include <iostream>
using namespace std;

string ans;
long long N, D, M, a;
const long long max_m = 1e6;
pair<int, int> job_requests[max_m];

bool check(long long m) {

    string t = "";
    long long day = 0;
    long long job_index = 0;
    bool stop = false;

    while (job_index < M && day < (N + D)) {
        day++;
        for (int i = 0; i < m; i++) {
            long long c_day = job_requests[job_index].first;
            if (day > c_day + D) {stop = true; break; }
            t.append(to_string(job_requests[job_index].second + 1));
            t.append(" ");
            job_index++;
        }
        t.append("0\n");
        if (stop) break;
    }

    for (long long i = day; i < N; i++) {
        t.append("0\n");
    }

    if (job_index == M) ans = t;
    return job_index == M;

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> D >> M;
    for (int i = 0; i < M; i++) {
        cin >> a;
        job_requests[i] = make_pair(a, i);
    }

    sort(job_requests, job_requests + M);

    long long l = 0, r = M;
    while (l < r) {
        long long m = l + (r - l) / 2;
        if (check(m)) {
            r = m;
        } else {
            l = m + 1;
        }
    }

    cout << r << "\n" << ans << "\n";

    return 0;

}

• Subtask 1: 40 / 100