Submission #1119372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119372		hujo	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	247 ms	31636 KiB

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 / 100