Submission #225792

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225792	2020-04-21T16:24:54 Z	Andrei_Cotor	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	331 ms	27000 KB

jobs

#include<iostream>
#include<algorithm>
#include<deque>
#include<vector>

using namespace std;

vector<int> Jobs[100005];
vector<int> Rez[100005];
int Day[1000005];
int n,d;

bool possible(int capacity)
{
    deque<int> Pending;
    for(int i=1; i<=n; i++)
    {
        Rez[i].clear();
        for(auto job:Jobs[i])
            Pending.push_back(job);

        for(int j=1; j<=capacity; j++)
        {
            if(Pending.empty())
                break;

            if(i-Day[Pending.front()]>d)
                return 0;

            Rez[i].push_back(Pending.front());
            Pending.pop_front();
        }
    }

    if(!Pending.empty())
        return 0;
    return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m;
    cin>>n>>d>>m;
    for(int i=1; i<=m; i++)
    {
        int x;
        cin>>x;
        Jobs[x].push_back(i);
        Day[i]=x;
    }

    int rez=0;
    for(int i=19; i>=0; i--)
    {
        if(!possible(rez+(1<<i)))
            rez+=(1<<i);
    }

    rez++;
    cout<<rez<<"\n";

    possible(rez);
    for(int i=1; i<=n; i++)
    {
        for(auto task:Rez[i])
            cout<<task<<" ";
        cout<<"0\n";
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	7700 KB	Output is correct
2	Correct	36 ms	7700 KB	Output is correct
3	Correct	36 ms	7700 KB	Output is correct
4	Correct	35 ms	7700 KB	Output is correct
5	Correct	37 ms	7824 KB	Output is correct
6	Correct	36 ms	7708 KB	Output is correct
7	Correct	36 ms	7824 KB	Output is correct
8	Correct	39 ms	7836 KB	Output is correct
9	Correct	45 ms	7676 KB	Output is correct
10	Correct	43 ms	7672 KB	Output is correct
11	Correct	37 ms	7548 KB	Output is correct
12	Correct	69 ms	9980 KB	Output is correct
13	Correct	102 ms	13544 KB	Output is correct
14	Correct	158 ms	17520 KB	Output is correct
15	Correct	148 ms	17656 KB	Output is correct
16	Correct	223 ms	21880 KB	Output is correct
17	Correct	283 ms	26616 KB	Output is correct
18	Correct	266 ms	25208 KB	Output is correct
19	Correct	331 ms	27000 KB	Output is correct
20	Correct	286 ms	26488 KB	Output is correct