Submission #925528

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925528	2024-02-11T22:54:34 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	359 ms	22424 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 = answer.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	23 ms	1856 KB	Output isn't correct
2	Incorrect	21 ms	1916 KB	Output isn't correct
3	Incorrect	19 ms	1920 KB	Output isn't correct
4	Incorrect	19 ms	2040 KB	Output isn't correct
5	Incorrect	19 ms	1924 KB	Output isn't correct
6	Incorrect	19 ms	1924 KB	Output isn't correct
7	Incorrect	18 ms	1916 KB	Output isn't correct
8	Incorrect	19 ms	2036 KB	Output isn't correct
9	Incorrect	44 ms	7024 KB	Output isn't correct
10	Incorrect	44 ms	7204 KB	Output isn't correct
11	Incorrect	35 ms	2192 KB	Output isn't correct
12	Incorrect	69 ms	4036 KB	Output isn't correct
13	Incorrect	103 ms	6764 KB	Output isn't correct
14	Incorrect	169 ms	9312 KB	Output isn't correct
15	Incorrect	171 ms	10480 KB	Output isn't correct
16	Incorrect	251 ms	13040 KB	Output isn't correct
17	Incorrect	288 ms	15600 KB	Output isn't correct
18	Incorrect	286 ms	16704 KB	Output isn't correct
19	Incorrect	359 ms	22424 KB	Output isn't correct
20	Incorrect	290 ms	15660 KB	Output isn't correct