Submission #1009786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1009786	2024-06-28T04:31:21 Z	devbelly	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	185 ms	20660 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	4824 KB	Output is correct
2	Correct	12 ms	4696 KB	Output is correct
3	Correct	13 ms	4820 KB	Output is correct
4	Correct	13 ms	4824 KB	Output is correct
5	Correct	13 ms	4820 KB	Output is correct
6	Correct	13 ms	4824 KB	Output is correct
7	Correct	11 ms	4820 KB	Output is correct
8	Correct	13 ms	4660 KB	Output is correct
9	Correct	23 ms	4820 KB	Output is correct
10	Correct	20 ms	4824 KB	Output is correct
11	Incorrect	16 ms	4564 KB	Output isn't correct
12	Incorrect	34 ms	6344 KB	Output isn't correct
13	Incorrect	54 ms	10432 KB	Output isn't correct
14	Incorrect	72 ms	10688 KB	Output isn't correct
15	Incorrect	93 ms	11964 KB	Output isn't correct
16	Incorrect	119 ms	16052 KB	Output isn't correct
17	Incorrect	142 ms	18612 KB	Output isn't correct
18	Correct	171 ms	19484 KB	Output is correct
19	Correct	185 ms	20660 KB	Output is correct
20	Incorrect	142 ms	19120 KB	Output isn't correct