Submission #925513

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925513	2024-02-11T21:44:26 Z	allw	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	301 ms	30072 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 (int j = 0; j < answer[i].size(); ++j) {
            std::cout << answer[i][j] << ' ';
        }
        std::cout << "0\n";
    }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < answer[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	19 ms	2512 KB	Output isn't correct
2	Incorrect	19 ms	2452 KB	Output isn't correct
3	Incorrect	19 ms	2512 KB	Output isn't correct
4	Incorrect	19 ms	2400 KB	Output isn't correct
5	Incorrect	19 ms	2592 KB	Output isn't correct
6	Incorrect	18 ms	2512 KB	Output isn't correct
7	Incorrect	19 ms	2512 KB	Output isn't correct
8	Incorrect	19 ms	2436 KB	Output isn't correct
9	Incorrect	45 ms	10964 KB	Output isn't correct
10	Incorrect	47 ms	10876 KB	Output isn't correct
11	Incorrect	25 ms	2896 KB	Output isn't correct
12	Incorrect	59 ms	5228 KB	Output isn't correct
13	Incorrect	86 ms	8884 KB	Output isn't correct
14	Incorrect	146 ms	12284 KB	Output isn't correct
15	Incorrect	141 ms	12908 KB	Output isn't correct
16	Incorrect	203 ms	17556 KB	Output isn't correct
17	Incorrect	242 ms	21380 KB	Output isn't correct
18	Incorrect	218 ms	21104 KB	Output isn't correct
19	Incorrect	301 ms	30072 KB	Output isn't correct
20	Incorrect	230 ms	21244 KB	Output isn't correct