oj.uz

답안 #925517

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

bool run(std::vector<int> a, int d, int x, std::vector<std::vector<int>>& answer, std::vector<std::vector<int>> ids) {
    int i = a.size() - d - 1;
    for (int j = a.size() - 1; i >= 0 && j >= 0; --j) {
        std::cout << i << ' ' << j << '\n';
        int v = std::min(a[i], x);
        a[i] -= v;
        
        while (v > 0) {
            //std::cout << "To " << j << " add " << ids[i].back() << '\n';
            answer[j].push_back(ids[i].back());
            ids[i].pop_back();
            --v;
        }
        if (i == j && a[i] != 0) return false;
        if (a[i] == 0) --i;
        if (a[i] < 0) break;
    }

    return true;
}

int main() {
    int n, d, m;
    std::cin >> n >> d >> m;
    std::vector<int> a(n + 1, 0);
    std::vector<std::vector<int>> ids(n + 1, std::vector<int>());

    for (int i = 0; i < m; ++i) {
        int tmp; std::cin >> tmp;
        a[tmp]++;
        ids[tmp].push_back(i + 1);
    }

    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, ids)) {
            r = m;
        } else {
            l = m;
        }
    }

    answer = std::vector<std::vector<int>>(n + 1, std::vector<int>());
    run(a, d, r, answer, ids);
    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 41 ms 3652 KB Expected EOLN
2 Incorrect 37 ms 3648 KB Expected EOLN
3 Incorrect 36 ms 3724 KB Expected EOLN
4 Incorrect 41 ms 3628 KB Expected EOLN
5 Incorrect 37 ms 3696 KB Expected EOLN
6 Incorrect 41 ms 3716 KB Expected EOLN
7 Incorrect 37 ms 3728 KB Expected EOLN
8 Incorrect 36 ms 3652 KB Expected EOLN
9 Incorrect 288 ms 31856 KB Expected EOLN
10 Incorrect 283 ms 31924 KB Expected EOLN
11 Incorrect 26 ms 2536 KB Expected EOLN
12 Incorrect 55 ms 4496 KB Expected EOLN
13 Incorrect 84 ms 7644 KB Expected EOLN
14 Incorrect 170 ms 11608 KB Expected EOLN
15 Incorrect 173 ms 11120 KB Expected EOLN
16 Incorrect 239 ms 16148 KB Expected EOLN
17 Incorrect 262 ms 19092 KB Expected EOLN
18 Incorrect 244 ms 19552 KB Expected EOLN
19 Runtime error 494 ms 46604 KB Memory limit exceeded
20 Incorrect 327 ms 19380 KB Expected EOLN