oj.uz

답안 #924700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924700 2024-02-09T13:50:08 Z tz74 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 624 ms 21692 KB 
#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];
#include <algorithm>

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

    for (int i = 1; i <= M; i++) {
        int d; cin >> d;
        // sorter[d].push_back(i);
        rq_base.push_back(make_pair(d, i));
    }
    std::sort(rq_base.begin(), rq_base.end());
    // 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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 2500 KB Output is correct
2 Correct 65 ms 2524 KB Output is correct
3 Correct 66 ms 2524 KB Output is correct
4 Correct 65 ms 2524 KB Output is correct
5 Correct 65 ms 2664 KB Output is correct
6 Correct 65 ms 2588 KB Output is correct
7 Correct 67 ms 2500 KB Output is correct
8 Correct 65 ms 2520 KB Output is correct
9 Correct 78 ms 3056 KB Output is correct
10 Correct 79 ms 2608 KB Output is correct
11 Correct 72 ms 2568 KB Output is correct
12 Correct 145 ms 4888 KB Output is correct
13 Correct 223 ms 7352 KB Output is correct
14 Correct 306 ms 9500 KB Output is correct
15 Correct 367 ms 11952 KB Output is correct
16 Correct 443 ms 14212 KB Output is correct
17 Correct 535 ms 16724 KB Output is correct
18 Correct 571 ms 18984 KB Output is correct
19 Correct 624 ms 21692 KB Output is correct
20 Correct 544 ms 16668 KB Output is correct