Submission #743203

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743203	2023-05-17T08:50:34 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	279 ms	20604 KB

jobs

#include <bits/stdc++.h>
using namespace std;
int day, deadline, work;
const int N = 100001;
int workday[N] = {};
vector<int> general;
vector<int> li[N] = {};

bool solve(int maxmachine)
{
    int workleft = work;
    int dayy = 1;
    vector<int> soil = general;
    while (workleft > 0 && !soil.empty())
    {
        for (int i = 0; i < maxmachine; ++i)
        {
            if (soil.back() + deadline < dayy)
                return false;
            else
            {
                workleft--;
                soil.pop_back();
            }
        }
        dayy++;
    }
    return true;
}

bool solveprint(int maxmachine)
{
    int workleft = work;
    int dayy = 1;
    vector<int> soil = general;
    while (workleft > 0 && !soil.empty())
    {
        for (int i = 0; i < maxmachine; ++i)
        {
            if (soil.back() + deadline < dayy)
                return false;
            else
            {
                cout << li[soil.back()].back() << " ";
                li[soil.back()].pop_back();
                workleft--;
                soil.pop_back();
            }
        }
        dayy++;
        cout << "0\n";
    }
    for(int i = dayy;i <= day;++i)
        cout << "0\n";
    return true;
}

int main()
{
    int a;
    cin >> day >> deadline >> work;
    for (int i = 0; i < work; ++i)
    {
        cin >> a;
        workday[a]++;
        li[a].push_back(i+1);
    }
    int maxwork = -1;
    for (int i = 1; i <= day - deadline; ++i)
    {
        maxwork = max(maxwork, workday[i]);
        for (int j = 1; j <= workday[i]; ++j)
            general.push_back(i);
    }
    reverse(general.begin(), general.end());
    int l = 1, r = work;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (solve(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << "\n";
    solveprint(l);
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	29 ms	4540 KB	Output isn't correct
2	Incorrect	33 ms	4380 KB	Output isn't correct
3	Incorrect	28 ms	4412 KB	Output isn't correct
4	Incorrect	32 ms	4400 KB	Output isn't correct
5	Incorrect	27 ms	4416 KB	Output isn't correct
6	Incorrect	28 ms	4356 KB	Output isn't correct
7	Incorrect	28 ms	4356 KB	Output isn't correct
8	Incorrect	28 ms	4328 KB	Output isn't correct
9	Incorrect	29 ms	4868 KB	Output isn't correct
10	Incorrect	30 ms	4832 KB	Output isn't correct
11	Incorrect	33 ms	4540 KB	Output isn't correct
12	Incorrect	67 ms	6456 KB	Output isn't correct
13	Incorrect	96 ms	9188 KB	Output isn't correct
14	Incorrect	146 ms	11176 KB	Output isn't correct
15	Incorrect	162 ms	12912 KB	Output isn't correct
16	Incorrect	209 ms	15460 KB	Output isn't correct
17	Incorrect	251 ms	18088 KB	Output isn't correct
18	Incorrect	243 ms	18812 KB	Output isn't correct
19	Incorrect	279 ms	20604 KB	Output isn't correct
20	Incorrect	250 ms	18080 KB	Output isn't correct