Submission #533091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
533091	2022-03-04T18:04:26 Z	Bench0310	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	274 ms	22748 KB

jobs

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,d,m;
    cin >> n >> d >> m;
    vector<int> v[n+1];
    for(int i=1;i<=m;i++)
    {
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    vector<vector<int>> res(n+1);
    auto go=[&](int lim)->bool
    {
        vector<int> cnt(n+1,0);
        int idx=n;
        res.assign(n+1,{});
        for(int i=n;i>=1;i--)
        {
            for(int id:v[i])
            {
                while(idx>i+d||cnt[idx]==lim) idx--;
                if(idx==i-1) return 0;
                res[idx].push_back(id);
                cnt[idx]++;
            }
        }
        return 1;
    };
    int l=0,r=m;
    while(l<r-1)
    {
        int lim=(l+r)/2;
        if(go(lim)) r=lim;
        else l=lim;
    }
    cout << r << "\n";
    go(r);
    for(int i=1;i<=n;i++)
    {
        for(int id:res[i]) cout << id << " ";
        cout << "0\n";
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	2756 KB	Output is correct
2	Correct	27 ms	2696 KB	Output is correct
3	Correct	29 ms	2668 KB	Output is correct
4	Correct	36 ms	2752 KB	Output is correct
5	Correct	27 ms	2696 KB	Output is correct
6	Correct	35 ms	2700 KB	Output is correct
7	Correct	29 ms	2680 KB	Output is correct
8	Correct	33 ms	2676 KB	Output is correct
9	Correct	61 ms	7552 KB	Output is correct
10	Correct	45 ms	7600 KB	Output is correct
11	Correct	27 ms	2368 KB	Output is correct
12	Correct	57 ms	4348 KB	Output is correct
13	Correct	90 ms	7636 KB	Output is correct
14	Correct	126 ms	10632 KB	Output is correct
15	Correct	154 ms	11228 KB	Output is correct
16	Correct	175 ms	14768 KB	Output is correct
17	Correct	225 ms	18976 KB	Output is correct
18	Correct	249 ms	17476 KB	Output is correct
19	Correct	274 ms	22748 KB	Output is correct
20	Correct	232 ms	19064 KB	Output is correct