Submission #925532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925532	2024-02-11T23:09:46 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	383 ms	28628 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	2384 KB	Expected EOLN
2	Incorrect	21 ms	2476 KB	Expected EOLN
3	Incorrect	19 ms	2384 KB	Expected EOLN
4	Incorrect	20 ms	2532 KB	Expected EOLN
5	Incorrect	20 ms	2380 KB	Expected EOLN
6	Incorrect	19 ms	2384 KB	Expected EOLN
7	Incorrect	20 ms	2380 KB	Expected EOLN
8	Incorrect	23 ms	2384 KB	Expected EOLN
9	Incorrect	49 ms	10056 KB	Expected EOLN
10	Incorrect	54 ms	10092 KB	Expected EOLN
11	Incorrect	36 ms	3152 KB	Expected EOLN
12	Incorrect	72 ms	5684 KB	Expected EOLN
13	Incorrect	125 ms	9588 KB	Expected EOLN
14	Incorrect	195 ms	13596 KB	Expected EOLN
15	Incorrect	218 ms	13084 KB	Expected EOLN
16	Incorrect	264 ms	16600 KB	Expected EOLN
17	Incorrect	328 ms	23408 KB	Expected EOLN
18	Incorrect	321 ms	22784 KB	Expected EOLN
19	Incorrect	383 ms	28628 KB	Expected EOLN
20	Incorrect	323 ms	23544 KB	Expected EOLN