Submission #925527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925527	2024-02-11T22:51:35 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	363 ms	22716 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 = a.size() - 1;

    for (int j = a.size() - 1; j >= 0; --j) {
        if (a[i].first > j) return false;

        int v = x;
        while (i >= 0 && v > 0 && j - a[i].first <= d) {
            answer[j].push_back(a[i].second);
            --i;
            --v;
        }
    }

    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;
        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";
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	21 ms	1920 KB	Output isn't correct
2	Incorrect	21 ms	1924 KB	Output isn't correct
3	Incorrect	20 ms	1924 KB	Output isn't correct
4	Incorrect	20 ms	1924 KB	Output isn't correct
5	Incorrect	20 ms	2036 KB	Output isn't correct
6	Incorrect	20 ms	1924 KB	Output isn't correct
7	Incorrect	20 ms	1920 KB	Output isn't correct
8	Incorrect	20 ms	1924 KB	Output isn't correct
9	Incorrect	47 ms	7188 KB	Output isn't correct
10	Incorrect	45 ms	7024 KB	Output isn't correct
11	Incorrect	35 ms	2132 KB	Output isn't correct
12	Incorrect	69 ms	4176 KB	Output isn't correct
13	Incorrect	105 ms	6652 KB	Output isn't correct
14	Incorrect	174 ms	9100 KB	Output isn't correct
15	Incorrect	175 ms	10584 KB	Output isn't correct
16	Incorrect	258 ms	13044 KB	Output isn't correct
17	Incorrect	300 ms	15544 KB	Output isn't correct
18	Incorrect	301 ms	16652 KB	Output isn't correct
19	Incorrect	363 ms	22716 KB	Output isn't correct
20	Incorrect	301 ms	15592 KB	Output isn't correct