Submission #1149809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149809		hs_zz27	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	213 ms	26928 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define str string
#define vi vector<int>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pi pair<int, int>
#define vpi vector<pi>
#define vvi vector<vector<int>>
#define si set<int>
#define ins insert
#define pb(a) push_back(a)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, b) for (int i = 0; i < (b); i++)
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    std::cin.tie(NULL)
#define coutyes cout << "YES" << endl;
#define coutno cout << "NO" << endl;
using namespace std;

ll n, d, m;
vvi vv(n);
bool good(vector<pair<int, int>> &v, int mid)
{
    vector<vi> schedule(n);
    int reqNum = 0;
    for (int day = 1; day <= n; day++)
    {
        for (int j = 0; j < mid; j++)
        {
            if (v[reqNum].first > day)
            {
                break;
            }
            if (v[reqNum].first + d >= day)
            {
                schedule[day - 1].push_back(v[reqNum++].second);
            }
            else
            {
                return false;
            }
            if (reqNum == m)
            {
                vv = schedule;
                return true;
            }
        }
    }
    return false;
}

void solve()
{
    cin >> n >> d >> m;
    vpi v(m);
    for (int i = 0; i < m; i++)
    {
        cin >> v[i].first;
        v[i].second = i + 1;
    }
    sort(all(v));
    int lo = 1, hi = m, ans = hi;
    while (hi >= lo)
    {
        int mid = lo + (hi - lo) / 2;
        if (good(v, mid))
        {
            ans = mid;
            hi = mid - 1;
        }
        else
            lo = mid + 1;
    }
    cout << ans << '\n';
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < vv[i].size(); j++)
        {
            cout << vv[i][j] << ' ';
        }
        cout << 0 << '\n';
    }
}

int main()
{
    fast_io;
    ll t;
    // cin >> t;

    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100