Submission #924704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924704	2024-02-09T13:54:04 Z	tz74	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	623 ms	21544 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;
}


void read_rq_base() {
    vector<int> sorter[(int) 1e6 + 1];

    for (int i = 1; i <= M; i++) {
        int d; cin >> d;
        sorter[d].push_back(i);
    }

    for (int d = 1; d <= 1e6; d++) {
        for (int id: sorter[d]) {
            rq_base.push_back(make_pair(d, id));
        }
    }
}

#include <algorithm>
int main(void) {
    cin >> N >> D >> M;
    // read_rq_base();
    for (int i = 1; i <= M; i++) {
        int d; cin >> d;
        rq_base.push_back(make_pair(d, i));
    }
    std::sort(rq_base.begin(), rq_base.end());

    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	2504 KB	Output is correct
2	Correct	66 ms	2500 KB	Output is correct
3	Correct	66 ms	2504 KB	Output is correct
4	Correct	64 ms	2488 KB	Output is correct
5	Correct	64 ms	2504 KB	Output is correct
6	Correct	64 ms	2492 KB	Output is correct
7	Correct	64 ms	2604 KB	Output is correct
8	Correct	64 ms	2496 KB	Output is correct
9	Correct	70 ms	2748 KB	Output is correct
10	Correct	74 ms	2608 KB	Output is correct
11	Correct	69 ms	2528 KB	Output is correct
12	Correct	148 ms	4752 KB	Output is correct
13	Correct	211 ms	7512 KB	Output is correct
14	Correct	307 ms	9492 KB	Output is correct
15	Correct	355 ms	11956 KB	Output is correct
16	Correct	418 ms	14308 KB	Output is correct
17	Correct	549 ms	16808 KB	Output is correct
18	Correct	567 ms	18960 KB	Output is correct
19	Correct	623 ms	21544 KB	Output is correct
20	Correct	538 ms	16688 KB	Output is correct