Submission #1009786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009786		devbelly	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	185 ms	20660 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() {

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

    int x = 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:65:9: warning: unused variable 'x' [-Wunused-variable]
   65 |     int x = solve(best, 1);
      |         ^

• Subtask 1: 60 / 100