Submission #668581

#	Time	Username	Problem	Language	Result	Execution time	Memory
668581		mutterpaneer	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	173 ms	16872 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(vector<pair<ll, ll>>& a, ll M) {
    // map<ll, ll> ans;

    ll day = 1;
    ll avail = M;
    ll i = 0;

    while (i < sz(a)) {
        // which day to allocate for a[i]th request
        if (avail > 0 && day >= a[i].ff) {
            // ans[a[i].ss] = day;
            if (a[i].ff + d < day) {
                dd(day);
                return false;
            }
            ++i;
            --avail;
        } else {
            day = max(day + 1, a[i].ff);
            avail = M;
        }
    }
    dd(day);
    return day + d <= n;
}

void solve() {
    cin >> n >> d >> m;
    vector<pair<ll, ll>> a(m);
    vector<ll> cnt(n);
    f(i, m) {
        cin >> x;
        a[i] = {x, i};
        ++cnt[x];
    }
    sort(all(a));
    ll mx = *max_element(all(cnt));
    ll L = 1;
    ll R = mx;
    ll ans = R;
    map<ll, ll> lim;
    // dd(a);
    while (L <= R) {
        ll M = L + (R - L) / 2;
        dd(L, M, R);
        if (pos(a, M)) {
            ans = min(ans, M);
            R = M - 1;
        } else {
            L = M + 1;
        }
    }
    cout << ans << nl;
}

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();
}

Compilation message (stderr)

jobs.cpp: In function 'bool pos(std::vector<std::pair<long long int, long long int> >&, long long int)':
jobs.cpp:5:17: warning: statement has no effect [-Wunused-value]
    5 | #define dd(...) 42
      |                 ^~
jobs.cpp:38:17: note: in expansion of macro 'dd'
   38 |                 dd(day);
      |                 ^~
jobs.cpp:5:17: warning: statement has no effect [-Wunused-value]
    5 | #define dd(...) 42
      |                 ^~
jobs.cpp:48:5: note: in expansion of macro 'dd'
   48 |     dd(day);
      |     ^~
jobs.cpp: In function 'void solve()':
jobs.cpp:5:17: warning: statement has no effect [-Wunused-value]
    5 | #define dd(...) 42
      |                 ^~
jobs.cpp:70:9: note: in expansion of macro 'dd'
   70 |         dd(L, M, R);
      |         ^~

• Subtask 1: 0 / 100