Submission #925518

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925518	2024-02-11T22:03:32 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	279 ms	26496 KB

jobs

#include <iostream>
#include <vector>

bool run(std::vector<int> a, int d, int x, std::vector<std::vector<int>>& answer, std::vector<std::vector<int>> ids) {
    int i = a.size() - d - 1;
    for (int j = a.size() - 1; i >= 0 && j >= 0; --j) {
        //std::cout << i << ' ' << j << '\n';
        int v = std::min(a[i], x);
        a[i] -= v;
        
        while (v > 0) {
            //std::cout << "To " << j << " add " << ids[i].back() << '\n';
            answer[j].push_back(ids[i].back());
            ids[i].pop_back();
            --v;
        }
        if (i == j && a[i] != 0) return false;
        if (a[i] == 0) --i;
        if (a[i] < 0) break;
    }

    return true;
}

int main() {
    int n, d, m;
    std::cin >> n >> d >> m;
    std::vector<int> a(n + 1, 0);
    std::vector<std::vector<int>> ids(n + 1, std::vector<int>());

    for (int i = 0; i < m; ++i) {
        int tmp; std::cin >> tmp;
        a[tmp]++;
        ids[tmp].push_back(i + 1);
    }

    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, ids)) {
            r = m;
        } else {
            l = m;
        }
    }

    answer = std::vector<std::vector<int>>(n + 1, std::vector<int>());
    run(a, d, r, answer, ids);
    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	18 ms	2244 KB	Output isn't correct
2	Incorrect	21 ms	2244 KB	Output isn't correct
3	Incorrect	19 ms	2256 KB	Output isn't correct
4	Incorrect	20 ms	2248 KB	Output isn't correct
5	Incorrect	19 ms	2272 KB	Output isn't correct
6	Incorrect	19 ms	2272 KB	Output isn't correct
7	Incorrect	18 ms	2256 KB	Output isn't correct
8	Incorrect	24 ms	2232 KB	Output isn't correct
9	Incorrect	43 ms	10620 KB	Output isn't correct
10	Incorrect	44 ms	10604 KB	Output isn't correct
11	Incorrect	25 ms	2396 KB	Output isn't correct
12	Incorrect	54 ms	4292 KB	Output isn't correct
13	Incorrect	85 ms	7600 KB	Output isn't correct
14	Incorrect	138 ms	10360 KB	Output isn't correct
15	Incorrect	157 ms	11116 KB	Output isn't correct
16	Incorrect	210 ms	14788 KB	Output isn't correct
17	Incorrect	243 ms	17912 KB	Output isn't correct
18	Incorrect	219 ms	18160 KB	Output isn't correct
19	Incorrect	279 ms	26496 KB	Output isn't correct
20	Incorrect	236 ms	17900 KB	Output isn't correct