Submission #1119372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119372	2024-11-27T01:48:23 Z	hujo	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	247 ms	31636 KB

jobs

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>

using namespace std;

struct Job {
    int id, start, end;
    Job(int id, int start, int end) : id(id), start(start), end(end) {}
};

int N, M;
vector<Job> jobs;

bool isGood(int machines) {
    queue<Job> q;
    for (const Job& j : jobs) {
        q.push(j);
    }
    for (int i = 1; i <= N; i++) {
        int nleft = machines;
        while (nleft > 0 && !q.empty()) {
            Job top = q.front();
            if (top.end < i || top.start > i) {
                break;
            } else {
                q.pop();
                nleft--;
            }
        }
    }
    return q.empty();
}

void printRes(int minMachines) {
    cout << minMachines << endl;
    queue<Job> q;
    for (const Job& j : jobs) {
        q.push(j);
    }
    for (int i = 1; i <= N; i++) {
        int nleft = minMachines;
        while (nleft > 0 && !q.empty()) {
            Job top = q.front();
            if (top.start > i) {
                break;
            } else {
                cout << top.id << " ";
                q.pop();
                nleft--;
            }
        }
        cout << "0\n";
    }
}

int binsearchLeft(int left, int right) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (isGood(mid)) {
        int res = binsearchLeft(left, mid - 1);
        return (res == -1) ? mid : res;
    } else {
        return binsearchLeft(mid + 1, right);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int D;
    cin >> N >> D >> M;
    for (int i = 1; i <= M; i++) {
        int id;
        cin >> id;
        jobs.emplace_back(i, id, id + D);
    }

    sort(jobs.begin(), jobs.end(), [](const Job& j1, const Job& j2) {
        return j1.end < j2.end;
    });

    int minMachines = binsearchLeft(0, M);
    printRes(minMachines);

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	3268 KB	Output is correct
2	Correct	26 ms	3304 KB	Output is correct
3	Correct	21 ms	3592 KB	Output is correct
4	Correct	21 ms	3312 KB	Output is correct
5	Correct	21 ms	3268 KB	Output is correct
6	Correct	18 ms	3300 KB	Output is correct
7	Correct	21 ms	3368 KB	Output is correct
8	Correct	20 ms	3784 KB	Output is correct
9	Correct	25 ms	3780 KB	Output is correct
10	Correct	36 ms	3524 KB	Output is correct
11	Correct	25 ms	3796 KB	Output is correct
12	Correct	57 ms	6840 KB	Output is correct
13	Correct	75 ms	10552 KB	Output is correct
14	Correct	131 ms	14236 KB	Output is correct
15	Correct	124 ms	17576 KB	Output is correct
16	Correct	181 ms	21648 KB	Output is correct
17	Correct	197 ms	25240 KB	Output is correct
18	Correct	201 ms	28052 KB	Output is correct
19	Correct	247 ms	31636 KB	Output is correct
20	Correct	189 ms	25140 KB	Output is correct