제출 #1149554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149554		hs_zz27	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	488 ms	11064 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;

bool good(vector<pair<int ,int>> &v, int mid)
{
    map<int, int> mp;
    for (int i = 0; i < m; i++)
    {
        mp[v[i].first]++;
    }
    for (auto i : mp)
    {
        int days = (i.second + mid - 1) / mid;
        if (days > d)
        {
            return false;
        }
    }
    return true;
}

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';
    vector<vi> schedule(n);
    int reqNum = 0;
    for (int day = 1; day <= n; day++)
    {
        for (int j = 0; j < ans; j++)
        {
            if (v[reqNum].first + d >= day)
            {
                schedule[day - 1].push_back(v[reqNum++].second);
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int job : schedule[i])
            cout << job << " ";
        cout << "0\n";
    }
}

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

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

• Subtask 1: 0 / 100