Submission #925514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925514	2024-02-11T21:50:53 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	281 ms	26468 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;
    int j = i + d;
    //std::cout << "======\n";
    while (i >= 0) {
        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;
        --j;
    }

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	2256 KB	Output isn't correct
2	Incorrect	20 ms	2408 KB	Output isn't correct
3	Incorrect	18 ms	2256 KB	Output isn't correct
4	Incorrect	19 ms	2276 KB	Output isn't correct
5	Incorrect	18 ms	2256 KB	Output isn't correct
6	Incorrect	18 ms	2252 KB	Output isn't correct
7	Incorrect	18 ms	2256 KB	Output isn't correct
8	Incorrect	18 ms	2256 KB	Output isn't correct
9	Incorrect	46 ms	10620 KB	Output isn't correct
10	Incorrect	45 ms	10612 KB	Output isn't correct
11	Incorrect	25 ms	2396 KB	Output isn't correct
12	Incorrect	55 ms	4532 KB	Output isn't correct
13	Incorrect	109 ms	7624 KB	Output isn't correct
14	Incorrect	137 ms	10268 KB	Output isn't correct
15	Incorrect	142 ms	11312 KB	Output isn't correct
16	Incorrect	200 ms	14488 KB	Output isn't correct
17	Incorrect	228 ms	17912 KB	Output isn't correct
18	Incorrect	216 ms	18072 KB	Output isn't correct
19	Incorrect	281 ms	26468 KB	Output isn't correct
20	Incorrect	239 ms	18256 KB	Output isn't correct