Submission #925535

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925535	2024-02-11T23:25:19 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	332 ms	23896 KB

jobs

#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) {
        if (a[i].first + d < j) {
            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;
        }

        if (i == a.size()) return true;
    } 
 
    return false;
}
 
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: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:14: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]
   14 |         while (i < a.size() && v > 0 && j >= a[i].first && j <= a[i].first + d) {
      |                ~~^~~~~~~~~~
jobs.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if (i == a.size()) return true;
      |             ~~^~~~~~~~~~~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	23 ms	2176 KB	Output isn't correct
2	Incorrect	18 ms	2036 KB	Output isn't correct
3	Incorrect	18 ms	1924 KB	Output isn't correct
4	Incorrect	20 ms	1924 KB	Output isn't correct
5	Incorrect	18 ms	1772 KB	Output isn't correct
6	Incorrect	18 ms	1924 KB	Output isn't correct
7	Incorrect	18 ms	1920 KB	Output isn't correct
8	Incorrect	18 ms	1924 KB	Output isn't correct
9	Correct	43 ms	8808 KB	Output is correct
10	Correct	42 ms	9500 KB	Output is correct
11	Correct	33 ms	2124 KB	Output is correct
12	Correct	69 ms	4260 KB	Output is correct
13	Correct	99 ms	6784 KB	Output is correct
14	Correct	165 ms	9412 KB	Output is correct
15	Correct	170 ms	9812 KB	Output is correct
16	Correct	241 ms	12656 KB	Output is correct
17	Correct	298 ms	16028 KB	Output is correct
18	Correct	296 ms	16836 KB	Output is correct
19	Correct	332 ms	23896 KB	Output is correct
20	Correct	274 ms	15940 KB	Output is correct