Submission #785690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
785690	2023-07-17T13:00:40 Z	raphaelp	Job Scheduling (CEOI12_jobs)	C++14	15 / 100	219 ms	24740 KB

jobs

#include <bits/stdc++.h>
using namespace std;

bool pos(int nb, vector<int> &Jcount, int D)
{
    int j = 0, b = 0;
    for (int i = 0; i < Jcount.size(); i++)
    {
        if (i - j > D)
            return false;
        int a = nb;
        while (a > 0 && j <= i)
        {
            if (a >= Jcount[j] - b)
            {
                a -= Jcount[j] - b;
                j++;
                b = 0;
            }
            else
            {
                b += a;
                a = 0;
            }
        }
    }
    if (j < Jcount.size())
        return false;
    return true;
}

int dico(int left, int right, vector<int> &Jcount, int D)
{
    int mil = (left + right) / 2;
    if (mil == left)
        if (pos(mil, Jcount, D))
            return mil;
        else
            return mil + 1;
    if (pos(mil, Jcount, D))
    {
        return dico(left, mil, Jcount, D);
    }
    else
        return dico(mil, right, Jcount, D);
}

int main()
{
    int N, D, M;
    cin >> N >> D >> M;
    vector<vector<int>> jobs(N);
    vector<int> Jcount(N, 0);
    for (int i = 0; i < M; i++)
    {
        int temp;
        cin >> temp;
        Jcount[temp - 1]++;
        jobs[temp - 1].push_back(i + 1);
    }
    int nbMach = dico(1, M + 1, Jcount, D);
    cout << nbMach << endl;
    int j = 0, b = 0;
    for (int i = 0; i < N; i++)
    {
        int a = nbMach;
        if (jobs[j].empty())
            j++;
        while (a > 0 && j <= i)
        {
            cout << jobs[j][jobs[j].size() - 1] << ' ';
            jobs[j].pop_back();
            a--;
            while (jobs[j].empty())
                j++;
        }
        cout << 0 << endl;
    }
}

Compilation message

jobs.cpp: In function 'bool pos(int, std::vector<int>&, int)':
jobs.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < Jcount.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
jobs.cpp:27:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (j < Jcount.size())
      |         ~~^~~~~~~~~~~~~~~
jobs.cpp: In function 'int dico(int, int, std::vector<int>&, int)':
jobs.cpp:35:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   35 |     if (mil == left)
      |        ^
jobs.cpp: In function 'int main()':
jobs.cpp:63:16: warning: unused variable 'b' [-Wunused-variable]
   63 |     int j = 0, b = 0;
      |                ^

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	22 ms	2916 KB	Execution killed with signal 11
2	Runtime error	20 ms	2848 KB	Execution killed with signal 11
3	Runtime error	20 ms	2856 KB	Execution killed with signal 11
4	Runtime error	21 ms	2864 KB	Execution killed with signal 11
5	Runtime error	23 ms	2904 KB	Execution killed with signal 11
6	Runtime error	22 ms	2812 KB	Execution killed with signal 11
7	Runtime error	20 ms	2868 KB	Execution killed with signal 11
8	Runtime error	27 ms	2800 KB	Execution killed with signal 11
9	Runtime error	25 ms	8132 KB	Execution killed with signal 11
10	Runtime error	24 ms	8108 KB	Execution killed with signal 11
11	Correct	26 ms	1740 KB	Output is correct
12	Incorrect	47 ms	3388 KB	Output isn't correct
13	Correct	64 ms	5644 KB	Output is correct
14	Runtime error	132 ms	10952 KB	Execution killed with signal 11
15	Correct	107 ms	8588 KB	Output is correct
16	Runtime error	166 ms	15928 KB	Execution killed with signal 11
17	Runtime error	219 ms	19588 KB	Execution killed with signal 11
18	Runtime error	189 ms	18616 KB	Execution killed with signal 11
19	Runtime error	202 ms	24740 KB	Execution killed with signal 11
20	Runtime error	202 ms	19508 KB	Execution killed with signal 11