Submission #924695

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924695	2024-02-09T13:39:43 Z	tz74	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	1000 ms	65536 KB

jobs

#include <iostream>
#include <vector>
#include <set>

using namespace std;

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

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

    for (int day = 1; day <= N; day++) {
        auto c_it = current.begin();
        while (c_it != current.end()) {
            if (*c_it <= day) {
                available++;
                c_it = current.erase(c_it);
            } else {
                break;
            }
        }

        auto p_it = rq.begin();
        while (p_it != rq.end()) {
            if (p_it->first <= day) {
                // must finish before day + D
                pending.insert(make_pair(p_it->first + D, p_it->second));
                p_it = rq.erase(p_it);
            } else {
                break;
            }
        }

        // 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.insert(day + 1);
            pending.erase(pending.begin());
            available--;
        }

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

    return true;
}

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

    for (int i = 1; i <= M; i++) {
        int d; cin >> d;
        rq_base.insert(make_pair(d, i));
    }

    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	498 ms	10612 KB	Output is correct
2	Correct	474 ms	10612 KB	Output is correct
3	Correct	473 ms	10868 KB	Output is correct
4	Correct	470 ms	10608 KB	Output is correct
5	Correct	473 ms	10576 KB	Output is correct
6	Correct	482 ms	10836 KB	Output is correct
7	Correct	481 ms	10620 KB	Output is correct
8	Correct	478 ms	10616 KB	Output is correct
9	Correct	403 ms	10656 KB	Output is correct
10	Correct	438 ms	10820 KB	Output is correct
11	Correct	345 ms	10832 KB	Output is correct
12	Correct	979 ms	21328 KB	Output is correct
13	Execution timed out	1065 ms	29468 KB	Time limit exceeded
14	Execution timed out	1025 ms	39760 KB	Time limit exceeded
15	Execution timed out	1041 ms	49236 KB	Time limit exceeded
16	Execution timed out	1071 ms	59736 KB	Time limit exceeded
17	Runtime error	665 ms	65536 KB	Execution killed with signal 9
18	Runtime error	527 ms	65536 KB	Execution killed with signal 9
19	Runtime error	598 ms	65536 KB	Execution killed with signal 9
20	Runtime error	690 ms	65536 KB	Execution killed with signal 9