Submission #925534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925534	2024-02-11T23:20:23 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	347 ms	23848 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) {
            
    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 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 = 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) {
      |                ~~^~~~~~~~~~
jobs.cpp:33: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]
   33 |     return i == a.size();
      |            ~~^~~~~~~~~~~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	1924 KB	Output isn't correct
2	Incorrect	19 ms	1992 KB	Output isn't correct
3	Incorrect	19 ms	1924 KB	Output isn't correct
4	Incorrect	19 ms	2036 KB	Output isn't correct
5	Incorrect	18 ms	2040 KB	Output isn't correct
6	Incorrect	19 ms	1924 KB	Output isn't correct
7	Incorrect	19 ms	1920 KB	Output isn't correct
8	Incorrect	19 ms	2024 KB	Output isn't correct
9	Correct	43 ms	8560 KB	Output is correct
10	Correct	45 ms	9388 KB	Output is correct
11	Correct	34 ms	2388 KB	Output is correct
12	Correct	70 ms	4260 KB	Output is correct
13	Correct	103 ms	6788 KB	Output is correct
14	Correct	175 ms	9512 KB	Output is correct
15	Correct	174 ms	9652 KB	Output is correct
16	Correct	243 ms	12732 KB	Output is correct
17	Correct	295 ms	16032 KB	Output is correct
18	Correct	294 ms	16804 KB	Output is correct
19	Correct	347 ms	23848 KB	Output is correct
20	Correct	284 ms	15876 KB	Output is correct