oj.uz

답안 #925528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925528 2024-02-11T22:54:34 Z allw Job Scheduling (CEOI12_jobs) C++17
0 / 100
 359 ms 22424 KB 
#include <iostream>
#include <vector>
#include <algorithm>

bool run(std::vector<std::pair<int, int>>& a, int d, int x, 
         std::vector<std::vector<int>>& answer) {
    
    int i = a.size() - 1;
    

    for (int j = answer.size() - 1; j >= 0; --j) {
        if (a[i].first > j) return false;

        int v = x;
        while (i >= 0 && v > 0 && j - a[i].first <= d) {
            answer[j].push_back(a[i].second);
            --i;
            --v;
        }
    }

    return true;
}

int main() {
    int n, d, m;
    std::cin >> n >> d >> m;
    std::vector<std::pair<int, int>> a(m, {0, 0});

    for (int i = 0; i < m; ++i) {
        std::cin >> a[i].first;
        a[i].second = i + 1;
    }
    std::sort(a.begin(), a.end());

    int l = 0;
    int r = n;
    std::vector<std::vector<int>> answer;
    // (l, r]
    while (l + 1 < r) {
        answer = std::vector<std::vector<int>>(n + 1, std::vector<int>());
        int m = (l + r) / 2;
        if (run(a, d, m, answer)) {
            r = m;
        } else {
            l = m;
        }
    }

    answer = std::vector<std::vector<int>>(n + 1, std::vector<int>());
    run(a, d, r, answer);
    std::cout << r << '\n';

    for (int i = 1; i <= n; ++i) {
        for (size_t j = 0; j < answer[i].size(); ++j) {
            std::cout << answer[i][j] << ' ';
        }
        std::cout << "0\n";
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 1856 KB Output isn't correct
2 Incorrect 21 ms 1916 KB Output isn't correct
3 Incorrect 19 ms 1920 KB Output isn't correct
4 Incorrect 19 ms 2040 KB Output isn't correct
5 Incorrect 19 ms 1924 KB Output isn't correct
6 Incorrect 19 ms 1924 KB Output isn't correct
7 Incorrect 18 ms 1916 KB Output isn't correct
8 Incorrect 19 ms 2036 KB Output isn't correct
9 Incorrect 44 ms 7024 KB Output isn't correct
10 Incorrect 44 ms 7204 KB Output isn't correct
11 Incorrect 35 ms 2192 KB Output isn't correct
12 Incorrect 69 ms 4036 KB Output isn't correct
13 Incorrect 103 ms 6764 KB Output isn't correct
14 Incorrect 169 ms 9312 KB Output isn't correct
15 Incorrect 171 ms 10480 KB Output isn't correct
16 Incorrect 251 ms 13040 KB Output isn't correct
17 Incorrect 288 ms 15600 KB Output isn't correct
18 Incorrect 286 ms 16704 KB Output isn't correct
19 Incorrect 359 ms 22424 KB Output isn't correct
20 Incorrect 290 ms 15660 KB Output isn't correct