oj.uz

Submission #648320

# Submission time Handle Problem Language Result Execution time Memory
648320 2022-10-06T02:41:40 Z DarkLightningLord Job Scheduling (CEOI12_jobs) C++17
100 / 100
 709 ms 27680 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3228 KB Output is correct
2 Correct 55 ms 3260 KB Output is correct
3 Correct 57 ms 3200 KB Output is correct
4 Correct 52 ms 3260 KB Output is correct
5 Correct 54 ms 3268 KB Output is correct
6 Correct 53 ms 3204 KB Output is correct
7 Correct 52 ms 3280 KB Output is correct
8 Correct 54 ms 3200 KB Output is correct
9 Correct 67 ms 3644 KB Output is correct
10 Correct 69 ms 3632 KB Output is correct
11 Correct 70 ms 3224 KB Output is correct
12 Correct 151 ms 6372 KB Output is correct
13 Correct 223 ms 10600 KB Output is correct
14 Correct 302 ms 12652 KB Output is correct
15 Correct 346 ms 14716 KB Output is correct
16 Correct 445 ms 20764 KB Output is correct
17 Correct 545 ms 22904 KB Output is correct
18 Correct 665 ms 25136 KB Output is correct
19 Correct 709 ms 27680 KB Output is correct
20 Correct 559 ms 22940 KB Output is correct