Submission #925517

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925517	2024-02-11T22:00:45 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	494 ms	46604 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	41 ms	3652 KB	Expected EOLN
2	Incorrect	37 ms	3648 KB	Expected EOLN
3	Incorrect	36 ms	3724 KB	Expected EOLN
4	Incorrect	41 ms	3628 KB	Expected EOLN
5	Incorrect	37 ms	3696 KB	Expected EOLN
6	Incorrect	41 ms	3716 KB	Expected EOLN
7	Incorrect	37 ms	3728 KB	Expected EOLN
8	Incorrect	36 ms	3652 KB	Expected EOLN
9	Incorrect	288 ms	31856 KB	Expected EOLN
10	Incorrect	283 ms	31924 KB	Expected EOLN
11	Incorrect	26 ms	2536 KB	Expected EOLN
12	Incorrect	55 ms	4496 KB	Expected EOLN
13	Incorrect	84 ms	7644 KB	Expected EOLN
14	Incorrect	170 ms	11608 KB	Expected EOLN
15	Incorrect	173 ms	11120 KB	Expected EOLN
16	Incorrect	239 ms	16148 KB	Expected EOLN
17	Incorrect	262 ms	19092 KB	Expected EOLN
18	Incorrect	244 ms	19552 KB	Expected EOLN
19	Runtime error	494 ms	46604 KB	Memory limit exceeded
20	Incorrect	327 ms	19380 KB	Expected EOLN