Submission #928062

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
928062	2024-02-15T19:56:11 Z	megaminion	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	175 ms	27248 KB

jobs

#include <bits/stdc++.h>
#define pb push_back
#define ins insert
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define endl '\n'
using namespace std;
const int M = 1e6;
const int N = 1e5;

int n, d, m;
int a[M], mp[N+1];
vector<int> v[N+1];
vector<int> p[N+1];

bool ok(int x, bool flag)
{
    bool ret = true;
    deque<int> dq;
    for(int i = 1; i <= n; ++i)
    {
        if(flag)
            v[i].clear();
        for(int j = 0; j < mp[i]; ++j)
        {
            dq.pb(i);
        }
        for(int j = 0; j < x; ++j)
        {
            if(dq.empty()) break;
            ret &= i - dq[0] <= d;
            if(flag)
            {
                v[i].pb(p[dq[0]].back());
                p[dq[0]].pop_back();
            }
            dq.pop_front();
        }
    }
    return ret;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>d>>m;
    for(int i = 0; i < m; ++i)
    {
        cin>>a[i];
        mp[a[i]]++;
        p[a[i]].pb(i+1);
    }
    int L = 1, R = 1e6, mid;
    while(L < R)
    {
        mid = L + (R - L) / 2;
        if(ok(mid, false))
        {
            R = mid;
        }
        else
        {
            L = mid+1;
        }
    }
    assert(ok(L, true));
    cout<<L<<endl;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < sz(v[i]); ++j)
        {
            cout<<v[i][j];
            if(j + 1 != sz(v[i])) cout<<" ";
            else cout<<" 0";
        }
        if(v[i].empty())
        {
            cout<<"0";
        }
        if(i != n) cout<<endl;
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	8928 KB	Output is correct
2	Correct	20 ms	8912 KB	Output is correct
3	Correct	20 ms	8936 KB	Output is correct
4	Correct	20 ms	8924 KB	Output is correct
5	Correct	20 ms	8976 KB	Output is correct
6	Correct	20 ms	9168 KB	Output is correct
7	Correct	20 ms	9176 KB	Output is correct
8	Correct	22 ms	8924 KB	Output is correct
9	Correct	27 ms	8748 KB	Output is correct
10	Correct	27 ms	8792 KB	Output is correct
11	Correct	20 ms	8796 KB	Output is correct
12	Correct	38 ms	10780 KB	Output is correct
13	Correct	57 ms	13908 KB	Output is correct
14	Correct	87 ms	18800 KB	Output is correct
15	Correct	95 ms	18772 KB	Output is correct
16	Correct	135 ms	22036 KB	Output is correct
17	Correct	149 ms	27160 KB	Output is correct
18	Correct	153 ms	25944 KB	Output is correct
19	Correct	175 ms	27248 KB	Output is correct
20	Correct	150 ms	27100 KB	Output is correct