제출 #661289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
661289		mutterpaneer	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	344 ms	38024 KiB

jobs

#include "bits/stdc++.h"
#ifdef LOCAL
#include "bits/debug.h"
#else
#define dd(...) 42
#endif
#define ll long long
#define ull unsigned long long
#define nl '\n'
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a) rend(a)
#define sz(a) ((int)a.size())
#define ff first
#define ss second
#define f(i, n) for (int i = 0; i < n; ++i)
// #define PROB_NAME "sliding"

using namespace std;

// const int INF = 1e9;
// const ll INFF = 1e18;
// const int M = 1e9 + 7;

ll d, h, n, m, k, p, q, x, y, z;

bool pos(ll cnt[], ll M) {
    ll dlay = 0;
    f(i, n) { dlay = max((cnt[i] + M - 1) / M, dlay); }
    return dlay <= d;
}

void solve() {
    cin >> n >> d >> m;
    ll a[m];
    f(i, m) cin >> a[i];
    ll cnt[n];
    f(i, n) cnt[i] = 0;
    f(i, m) cnt[a[i]]++;
    ll L = 1;
    ll R = 1e9;
    ll ans = R;
    while (L <= R) {
        ll M = L + (R - L) / 2;
        if (pos(cnt, M)) {
            ans = min(ans, M);
            R = M - 1;
        } else {
            L = M + 1;
        }
    }
    cout << ans << nl;
    vector<pair<ll, ll>> A;
    f(i, m) A.push_back({a[i], i + 1});
    sort(all(A));
    map<ll, vector<ll>> M;
    // f(i, n) cerr << cnt[i] << " ";
    ll i = 0;
    ll day = 1;
    while (i < m && day <= n) {
        while (i < m && sz(M[day]) < ans) {
            M[day].push_back(A[i].ss);
            ++i;
        }
        ++day;
    }
    ll pr = 0;
    for (auto& e : M) {
        f(ii, sz(e.ss)) cout << e.ss[ii] << ' ';
        cout << '0' << nl;
        ++pr;
    }
    while (pr < n) {
        cout << 0 << nl;
        ++pr;
    }
}

void TESTCASES() {
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef PROB_NAME
    freopen(PROB_NAME ".in", "r", stdin);
    freopen(PROB_NAME ".out", "w", stdout);
#endif
    TESTCASES();
}

• Subtask 1: 0 / 100