oj.uz

Submission #960447

# Submission time Handle Problem Language Result Execution time Memory
960447 2024-04-10T13:23:48 Z Nelt Job Scheduling (CEOI12_jobs) C++17
58 / 100
 158 ms 27440 KB 
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

void solve()
{
    ll n, d, m;
    cin >> n >> d >> m;
    vector<ll> v[n + 1];
    ll tm[m + 1];
    for (ll i = 1; i <= m; i++)
    {
        cin >> tm[i];
        v[tm[i]].push_back(i);
    }
    ll l = 1, r = m;
    queue<ll> q;
    vector<ll> ans[n + 1];
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        bool ok = true;
        while (!q.empty())
            q.pop();
        for (ll i = 1, cnt; i <= n; i++)
        {
            for (ll j : v[i])
                q.push(j);
            if (!q.empty() and tm[q.front()] + d < i)
            {
                ok = false;
                break;
            }
            cnt = 0;
            while (!q.empty() and cnt < mid)
                cnt++, q.pop();
        }
        if (ok)
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ++r << endl;
    for (ll i = 1, cnt; i <= n; i++)
    {
        for (ll j : v[i])
            q.push(j);
        cnt = 0;
        while (!q.empty() and cnt < r)
            cout << q.front() << " ", cnt++, q.pop();
        cout << "0\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        solve();
    cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
58.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 3800 KB Partially correct
2 Partially correct 16 ms 3800 KB Partially correct
3 Partially correct 15 ms 3800 KB Partially correct
4 Partially correct 16 ms 3872 KB Partially correct
5 Partially correct 15 ms 3812 KB Partially correct
6 Partially correct 15 ms 3800 KB Partially correct
7 Partially correct 15 ms 3800 KB Partially correct
8 Partially correct 16 ms 3800 KB Partially correct
9 Partially correct 20 ms 7760 KB Partially correct
10 Partially correct 21 ms 7772 KB Partially correct
11 Correct 21 ms 2932 KB Output is correct
12 Correct 32 ms 5204 KB Output is correct
13 Partially correct 50 ms 9068 KB Partially correct
14 Correct 79 ms 12088 KB Output is correct
15 Correct 85 ms 13960 KB Output is correct
16 Correct 120 ms 17392 KB Output is correct
17 Partially correct 149 ms 21328 KB Partially correct
18 Correct 139 ms 21376 KB Output is correct
19 Partially correct 158 ms 27440 KB Partially correct
20 Partially correct 140 ms 21264 KB Partially correct