oj.uz

Submission #925537

# Submission time Handle Problem Language Result Execution time Memory
925537 2024-02-11T23:32:39 Z allw Job Scheduling (CEOI12_jobs) C++17
75 / 100
 1000 ms 16540 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 = 0;
    for (int j = 1; i < a.size() && j < answer.size(); ++j) {
        for (int k = 0; i < a.size() && k < x; ++k) {

            if (a[i].first + d < j) return false;
            if (j >= a[i].first && j <= a[i].first + d) {
                answer[j].push_back(a[i].second);
                ++i;
            }
        }
    } 
 
    return i == a.size();
}
 
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 = m;
    std::vector<std::vector<int>> answer;
    // (l, r]
    while (l + 1 < r) {
        answer = std::vector<std::vector<int>>(n + 1, std::vector<int>());
        int middle = (l + r) / 2;
        if (run(a, d, middle, answer)) {
            r = middle;
        } else {
            l = middle;
        }
    }
 
    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:8: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]
    8 |     for (int j = 1; i < a.size() && j < answer.size(); ++j) {
      |                     ~~^~~~~~~~~~
jobs.cpp:8:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int j = 1; i < a.size() && j < answer.size(); ++j) {
      |                                     ~~^~~~~~~~~~~~~~~
jobs.cpp:9:27: 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 k = 0; i < a.size() && k < x; ++k) {
      |                         ~~^~~~~~~~~~
jobs.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     return i == a.size();
      |            ~~^~~~~~~~~~~

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2468 KB Output is correct
2 Correct 42 ms 2600 KB Output is correct
3 Correct 48 ms 2604 KB Output is correct
4 Correct 62 ms 2492 KB Output is correct
5 Correct 61 ms 2628 KB Output is correct
6 Correct 70 ms 2720 KB Output is correct
7 Correct 75 ms 2460 KB Output is correct
8 Correct 92 ms 2604 KB Output is correct
9 Correct 46 ms 8564 KB Output is correct
10 Correct 46 ms 9508 KB Output is correct
11 Correct 115 ms 2116 KB Output is correct
12 Correct 216 ms 4164 KB Output is correct
13 Correct 374 ms 6788 KB Output is correct
14 Execution timed out 1061 ms 5444 KB Time limit exceeded
15 Correct 606 ms 9696 KB Output is correct
16 Execution timed out 1068 ms 6920 KB Time limit exceeded
17 Execution timed out 1046 ms 7420 KB Time limit exceeded
18 Correct 944 ms 16540 KB Output is correct
19 Execution timed out 1028 ms 16368 KB Time limit exceeded
20 Execution timed out 1057 ms 7532 KB Time limit exceeded