oj.uz

Submission #960446

# Submission time Handle Problem Language Result Execution time Memory
960446 2024-04-10T13:21:06 Z Nelt Job Scheduling (CEOI12_jobs) C++17
80 / 100
 212 ms 49936 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> tmp[n + 1], ans[n + 1];
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        bool ok = true;
        while (!q.empty())
            q.pop();
        for (ll i = 1; i <= n; i++)
        {
            tmp[i].clear();
            for (ll j : v[i])
                q.push(j);
            if (!q.empty() and tm[q.front()] + d < i)
            {
                ok = false;
                break;
            }
            while (!q.empty() and tmp[i].size() < mid)
                tmp[i].push_back(q.front()), q.pop();
        }
        if (ok)
        {
            r = mid - 1;
            for (ll i = 1; i <= n; i++)
                ans[i] = tmp[i];
        }
        else
            l = mid + 1;
    }
    cout << ++r << endl;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j : ans[i])
            cout << j << " ";
        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";
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:36:49: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   36 |             while (!q.empty() and tmp[i].size() < mid)
      |                                   ~~~~~~~~~~~~~~^~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5836 KB Output is correct
2 Correct 16 ms 6012 KB Output is correct
3 Correct 27 ms 5848 KB Output is correct
4 Correct 22 ms 6008 KB Output is correct
5 Correct 16 ms 6052 KB Output is correct
6 Correct 17 ms 5848 KB Output is correct
7 Correct 23 ms 5848 KB Output is correct
8 Correct 17 ms 5844 KB Output is correct
9 Correct 29 ms 12144 KB Output is correct
10 Correct 28 ms 12380 KB Output is correct
11 Correct 22 ms 5208 KB Output is correct
12 Correct 46 ms 10092 KB Output is correct
13 Correct 57 ms 16976 KB Output is correct
14 Correct 112 ms 23028 KB Output is correct
15 Correct 96 ms 25424 KB Output is correct
16 Correct 167 ms 32200 KB Output is correct
17 Runtime error 212 ms 39760 KB Memory limit exceeded
18 Runtime error 183 ms 40464 KB Memory limit exceeded
19 Runtime error 210 ms 49936 KB Memory limit exceeded
20 Runtime error 211 ms 41952 KB Memory limit exceeded