oj.uz

답안 #925532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925532 2024-02-11T23:09:46 Z allw Job Scheduling (CEOI12_jobs) C++17
0 / 100
 383 ms 28628 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) {
            
    if (false) {
    for (int i = 0; i < a.size(); ++i) {
        std::cout << '(' << a[i].first << ", " << a[i].second << ") ";
    }
    std::cout << '\n';
    }

    int i = 0;
    for (int j = 1; i < a.size() && j < answer.size(); ++j) {
        //std::cout << i << ' ' << a[i].first << ' ' << j << '\n';
        if (a[i].first + d < j) {
        //    std::cout << "======\n";
            return false;
        }

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

    // std::cout << "======\n";

    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;
        std::cout << m << ' ' << run(a, d, m, answer) << '\n';
        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";
    }
}

Compilation message

jobs.cpp: In function 'bool run(std::vector<std::pair<int, int> >&, int, int, std::vector<std::vector<int> >&)':
jobs.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
jobs.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int j = 1; i < a.size() && j < answer.size(); ++j) {
      |                     ~~^~~~~~~~~~
jobs.cpp:16:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int j = 1; i < a.size() && j < answer.size(); ++j) {
      |                                     ~~^~~~~~~~~~~~~~~
jobs.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         while (i < a.size() && v > 0 && j >= a[i].first && j <= a[i].first + d) {
      |                ~~^~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 2384 KB Expected EOLN
2 Incorrect 21 ms 2476 KB Expected EOLN
3 Incorrect 19 ms 2384 KB Expected EOLN
4 Incorrect 20 ms 2532 KB Expected EOLN
5 Incorrect 20 ms 2380 KB Expected EOLN
6 Incorrect 19 ms 2384 KB Expected EOLN
7 Incorrect 20 ms 2380 KB Expected EOLN
8 Incorrect 23 ms 2384 KB Expected EOLN
9 Incorrect 49 ms 10056 KB Expected EOLN
10 Incorrect 54 ms 10092 KB Expected EOLN
11 Incorrect 36 ms 3152 KB Expected EOLN
12 Incorrect 72 ms 5684 KB Expected EOLN
13 Incorrect 125 ms 9588 KB Expected EOLN
14 Incorrect 195 ms 13596 KB Expected EOLN
15 Incorrect 218 ms 13084 KB Expected EOLN
16 Incorrect 264 ms 16600 KB Expected EOLN
17 Incorrect 328 ms 23408 KB Expected EOLN
18 Incorrect 321 ms 22784 KB Expected EOLN
19 Incorrect 383 ms 28628 KB Expected EOLN
20 Incorrect 323 ms 23544 KB Expected EOLN