Submission #715685

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
715685	2023-03-27T13:58:20 Z	12345678	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	154 ms	16688 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int N, D, M, d;
vector<vector<int>> v(100005);

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>N>>D>>M;
    for (int i=1; i<=M; i++)
    {
        cin>>d;
        v[d].push_back(i);
    }
    int l=1, r=M;
    while (l<r)
    {
        int md=(l+r)/2;
        bool can=true;
        deque<pair<int, int>> dq;
        for (int i=1; i<=N; i++)
        {
            if (v[i].size()!=0)
                dq.push_back({i+D, v[i].size()});
            int mc=md;
            while (mc>0&&!dq.empty())
            {
                int cw=dq.front().second;
                if (mc>=cw)
                {
                    mc-=cw;
                    dq.pop_front();
                }
                else
                {
                    int dl=dq.front().first;
                    dq.pop_front();
                    dq.push_front({dl, cw-mc});
                    mc=0;
                    break;
                }
            }
            if (!dq.empty())
            {
                if (dq.front().first<=i)
                {
                    can=false;
                    break;
                }
            }
        }
        if (can)
            r=md;
        else
            l=md+1;
    }
    cout<<l<<'\n';
    queue<int> q;
    for (int i=1; i<=N; i++)
    {
        int left=l;
        for (auto a:v[i])
            q.push(a);
        while (!q.empty()&&left>0)
        {
            left--;
            cout<<q.front()<<' ';
            q.pop();
        }
        cout<<"0\n";
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	4308 KB	Output is correct
2	Correct	17 ms	4260 KB	Output is correct
3	Correct	18 ms	4388 KB	Output is correct
4	Correct	15 ms	4308 KB	Output is correct
5	Correct	20 ms	4352 KB	Output is correct
6	Correct	16 ms	4308 KB	Output is correct
7	Correct	17 ms	4356 KB	Output is correct
8	Correct	16 ms	4300 KB	Output is correct
9	Correct	28 ms	4304 KB	Output is correct
10	Correct	29 ms	4324 KB	Output is correct
11	Correct	17 ms	4204 KB	Output is correct
12	Correct	32 ms	5764 KB	Output is correct
13	Correct	57 ms	7900 KB	Output is correct
14	Correct	89 ms	9920 KB	Output is correct
15	Correct	82 ms	10964 KB	Output is correct
16	Correct	127 ms	13388 KB	Output is correct
17	Correct	147 ms	15820 KB	Output is correct
18	Correct	131 ms	15436 KB	Output is correct
19	Correct	154 ms	16688 KB	Output is correct
20	Correct	152 ms	15672 KB	Output is correct