Submission #924702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924702	2024-02-09T13:52:38 Z	tz74	Job Scheduling (CEOI12_jobs)	C++17	65 / 100	545 ms	47072 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;
}

// #include <algorithm>

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));
        }
    }
}

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

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	26380 KB	Output is correct
2	Correct	79 ms	26420 KB	Output is correct
3	Correct	80 ms	26420 KB	Output is correct
4	Correct	79 ms	26420 KB	Output is correct
5	Correct	79 ms	26376 KB	Output is correct
6	Correct	82 ms	26380 KB	Output is correct
7	Correct	80 ms	26420 KB	Output is correct
8	Correct	80 ms	26420 KB	Output is correct
9	Correct	81 ms	26452 KB	Output is correct
10	Correct	84 ms	26592 KB	Output is correct
11	Correct	78 ms	26364 KB	Output is correct
12	Correct	140 ms	29024 KB	Output is correct
13	Correct	199 ms	31652 KB	Output is correct
14	Runtime error	289 ms	34400 KB	Memory limit exceeded
15	Runtime error	335 ms	36736 KB	Memory limit exceeded
16	Runtime error	387 ms	39500 KB	Memory limit exceeded
17	Runtime error	501 ms	42628 KB	Memory limit exceeded
18	Runtime error	492 ms	44548 KB	Memory limit exceeded
19	Runtime error	537 ms	47072 KB	Memory limit exceeded
20	Runtime error	545 ms	42188 KB	Memory limit exceeded