Submission #924698

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924698	2024-02-09T13:49:08 Z	tz74	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	552 ms	52644 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];

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

    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 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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	26572 KB	Output is correct
2	Correct	70 ms	26600 KB	Output is correct
3	Correct	70 ms	26516 KB	Output is correct
4	Correct	70 ms	26500 KB	Output is correct
5	Correct	69 ms	26568 KB	Output is correct
6	Correct	70 ms	26564 KB	Output is correct
7	Correct	78 ms	26568 KB	Output is correct
8	Correct	70 ms	26564 KB	Output is correct
9	Correct	68 ms	26668 KB	Output is correct
10	Correct	73 ms	26664 KB	Output is correct
11	Correct	73 ms	27032 KB	Output is correct
12	Correct	130 ms	29268 KB	Output is correct
13	Runtime error	227 ms	32908 KB	Memory limit exceeded
14	Runtime error	279 ms	35708 KB	Memory limit exceeded
15	Runtime error	316 ms	38144 KB	Memory limit exceeded
16	Runtime error	374 ms	41832 KB	Memory limit exceeded
17	Runtime error	474 ms	48508 KB	Memory limit exceeded
18	Runtime error	484 ms	49748 KB	Memory limit exceeded
19	Runtime error	552 ms	52644 KB	Memory limit exceeded
20	Runtime error	471 ms	48720 KB	Memory limit exceeded