Submission #925533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925533	2024-02-11T23:10:36 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	332 ms	23852 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 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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	1920 KB	Output isn't correct
2	Incorrect	18 ms	2176 KB	Output isn't correct
3	Incorrect	18 ms	1920 KB	Output isn't correct
4	Incorrect	18 ms	1920 KB	Output isn't correct
5	Incorrect	18 ms	1924 KB	Output isn't correct
6	Incorrect	18 ms	2036 KB	Output isn't correct
7	Incorrect	18 ms	1924 KB	Output isn't correct
8	Incorrect	18 ms	1924 KB	Output isn't correct
9	Correct	41 ms	8676 KB	Output is correct
10	Correct	42 ms	9664 KB	Output is correct
11	Correct	35 ms	2120 KB	Output is correct
12	Correct	67 ms	4148 KB	Output is correct
13	Correct	102 ms	6652 KB	Output is correct
14	Correct	165 ms	9424 KB	Output is correct
15	Correct	166 ms	9648 KB	Output is correct
16	Correct	250 ms	12656 KB	Output is correct
17	Correct	276 ms	16032 KB	Output is correct
18	Correct	293 ms	16788 KB	Output is correct
19	Correct	332 ms	23852 KB	Output is correct
20	Correct	283 ms	16032 KB	Output is correct