oj.uz

답안 #924695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924695 2024-02-09T13:39:43 Z tz74 Job Scheduling (CEOI12_jobs) C++17
60 / 100
 1000 ms 65536 KB 
#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

# 결과 실행 시간 메모리 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