Submission #925536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925536	2024-02-11T23:28:04 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	455 ms	23956 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) {
        
        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;
            }
        }

        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:10: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]
   10 |         for (int k = 0; i < a.size() && k < x; ++k) {
      |                         ~~^~~~~~~~~~
jobs.cpp:18: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]
   18 |         if (i == a.size()) return true;
      |             ~~^~~~~~~~~~~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	21 ms	1924 KB	Output isn't correct
2	Incorrect	21 ms	1924 KB	Output isn't correct
3	Incorrect	23 ms	1924 KB	Output isn't correct
4	Incorrect	24 ms	1924 KB	Output isn't correct
5	Incorrect	24 ms	1924 KB	Output isn't correct
6	Incorrect	29 ms	1924 KB	Output isn't correct
7	Incorrect	27 ms	1924 KB	Output isn't correct
8	Incorrect	28 ms	1924 KB	Output isn't correct
9	Correct	46 ms	8556 KB	Output is correct
10	Correct	48 ms	9384 KB	Output is correct
11	Correct	35 ms	2236 KB	Output is correct
12	Correct	68 ms	4280 KB	Output is correct
13	Correct	106 ms	6652 KB	Output is correct
14	Correct	274 ms	9520 KB	Output is correct
15	Correct	198 ms	9652 KB	Output is correct
16	Correct	349 ms	12956 KB	Output is correct
17	Correct	380 ms	16020 KB	Output is correct
18	Correct	335 ms	16788 KB	Output is correct
19	Correct	455 ms	23956 KB	Output is correct
20	Correct	380 ms	15836 KB	Output is correct