Submission #648320

#	Time	Username	Problem	Language	Result	Execution time	Memory
648320		DarkLightningLord	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	709 ms	27680 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;

    for (int day = 1; day <= N; day++) {
        long long c_m = 0;
        while (c_m < m && job_index < M && job_requests[job_index].first <= day) {
            if (job_requests[job_index].first + D >= day) {
                t.append(to_string(job_requests[job_index].second + 1));
                t.append(" ");
                c_m++;
                job_index++;
            } else return false;
        }
        t.append("0\n");
    }

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

//    change: cannot work after day M therefore for loop for days and within a for loop for machines?
//    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) return false;
//            t.append(to_string(job_requests[job_index].second + 1));
//            t.append(" ");
//            job_index++;
//        }
//        t.append("0\n");
//    }
//
//    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;

}

/*
Test Case 1:
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
Test Case 2:
1 1 6
1 1 1 1 1 1
Test Case 3:
2 1 6
1 1 1 1 1 1
 */

• Subtask 1: 100 / 100