Submission #924700

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924700	2024-02-09T13:50:08 Z	tz74	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	624 ms	21692 KB

jobs

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int N, D, M;
deque<pair<int, int> > rq_base;

bool check(int n_machines, bool show) {
    int available = n_machines;
    deque<int> current;
    deque<pair<int, int> > pending;
    deque<pair<int, int> > rq = rq_base;

    for (int day = 1; day <= N; day++) {
        while (!current.empty() && current.front() <= day) {
            available++;
            current.pop_front();
        }

        while (!rq.empty() && rq.front().first <= day) {
            auto f = rq.front();
            pending.push_back(make_pair(f.first + D, f.second));
            rq.pop_front();
        }

        // pop the ones that have tightest requirements
        while (available != 0 && !pending.empty()) {
            int need = pending.begin()->first;
            if (need < day) {
                return false;
            }

            if (show) printf("%d ", pending.begin()->second);

            // will get this printer back the next day
            current.push_back(day + 1);
            pending.erase(pending.begin());
            available--;
        }

        if (show) printf("0\n");
    }

    return true;
}

// vector<int> sorter[(int) 1e6 + 1];
#include <algorithm>

int main(void) {
    cin >> N >> D >> M;

    for (int i = 1; i <= M; i++) {
        int d; cin >> d;
        // sorter[d].push_back(i);
        rq_base.push_back(make_pair(d, i));
    }
    std::sort(rq_base.begin(), rq_base.end());
    // for (int d = 1; d <= 1e6; d++) {
    //     for (int id: sorter[d]) {
    //         rq_base.push_back(make_pair(d, id));
    //     }
    // }

    int lo = 1, hi = 1e6;
    while (lo < hi) {
        int mid = (lo + hi) / 2;

        if (check(mid, 0)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    printf("%d\n", lo);
    check(lo, 1);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	2500 KB	Output is correct
2	Correct	65 ms	2524 KB	Output is correct
3	Correct	66 ms	2524 KB	Output is correct
4	Correct	65 ms	2524 KB	Output is correct
5	Correct	65 ms	2664 KB	Output is correct
6	Correct	65 ms	2588 KB	Output is correct
7	Correct	67 ms	2500 KB	Output is correct
8	Correct	65 ms	2520 KB	Output is correct
9	Correct	78 ms	3056 KB	Output is correct
10	Correct	79 ms	2608 KB	Output is correct
11	Correct	72 ms	2568 KB	Output is correct
12	Correct	145 ms	4888 KB	Output is correct
13	Correct	223 ms	7352 KB	Output is correct
14	Correct	306 ms	9500 KB	Output is correct
15	Correct	367 ms	11952 KB	Output is correct
16	Correct	443 ms	14212 KB	Output is correct
17	Correct	535 ms	16724 KB	Output is correct
18	Correct	571 ms	18984 KB	Output is correct
19	Correct	624 ms	21692 KB	Output is correct
20	Correct	544 ms	16668 KB	Output is correct