Submission #1009785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009785		devbelly	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	4 ms	2876 KiB

jobs

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)

using namespace std;

typedef pair<int, int> pii;

int N, D, M;
vector<pii> vt;
vector<int> adj[100005];

bool solve(int x, int s) {

    int start = N - D;
    int p = 0;
    int ok = 0;
    while (start != 0) {

        int q = 0;

        while (q < x && p < M && (start >= vt[p].first && vt[p].first + D >= start)) {
            if (s) {
                adj[start].emplace_back(vt[p].second + 1);
            }
            ok += 1;
            q += 1;
            p += 1;
        }
        start -= 1;
    }
    return ok == M;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> D >> M;
    rep(i, M) {
        int x;
        cin >> x;
        vt.emplace_back(x, i);
    }

    sort(vt.rbegin(), vt.rend());
    // for (auto [a, b] : vt) {
    //     cout << a << ' ' << b + 1 << '\n';
    // }
    int lo = 1;
    int hi = M;
    int best = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (solve(mid, 0)) {
            best = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    solve(best, 1);
    cout << best << '\n';
    REP(i, N) {
        for (auto x : adj[i]) {
            cout << x << ' ';
        }
        cout << "0\n";
    }

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
jobs.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100