oj.uz

답안 #925513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925513 2024-02-11T21:44:26 Z allw Job Scheduling (CEOI12_jobs) C++17
0 / 100
 301 ms 30072 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;
    int j = i + d;
    //std::cout << "======\n";
    while (i >= 0) {
        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;
        --j;
    }

    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 (int j = 0; j < answer[i].size(); ++j) {
            std::cout << answer[i][j] << ' ';
        }
        std::cout << "0\n";
    }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < answer[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 2512 KB Output isn't correct
2 Incorrect 19 ms 2452 KB Output isn't correct
3 Incorrect 19 ms 2512 KB Output isn't correct
4 Incorrect 19 ms 2400 KB Output isn't correct
5 Incorrect 19 ms 2592 KB Output isn't correct
6 Incorrect 18 ms 2512 KB Output isn't correct
7 Incorrect 19 ms 2512 KB Output isn't correct
8 Incorrect 19 ms 2436 KB Output isn't correct
9 Incorrect 45 ms 10964 KB Output isn't correct
10 Incorrect 47 ms 10876 KB Output isn't correct
11 Incorrect 25 ms 2896 KB Output isn't correct
12 Incorrect 59 ms 5228 KB Output isn't correct
13 Incorrect 86 ms 8884 KB Output isn't correct
14 Incorrect 146 ms 12284 KB Output isn't correct
15 Incorrect 141 ms 12908 KB Output isn't correct
16 Incorrect 203 ms 17556 KB Output isn't correct
17 Incorrect 242 ms 21380 KB Output isn't correct
18 Incorrect 218 ms 21104 KB Output isn't correct
19 Incorrect 301 ms 30072 KB Output isn't correct
20 Incorrect 230 ms 21244 KB Output isn't correct