Submission #1312013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312013		quacksire	Job Scheduling (CEOI12_jobs)	C++20	55 / 100	122 ms	13876 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int pos;
    int index;
    Job(int p, int i) : pos(p), index(i) {}
    bool operator<(const Job &other) const {
        return pos < other.pos;
    }
};

bool work(int num, int d, vector<Job> &array) {
    int m = array.size();
    int batches = (m + num - 1) / num;
    for (int i = 0; i < batches; i++) {
        if (array[i * num].pos + d < i)
            return false;
    }
    return true;
}

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

    int n, d, m;
    cin >> n >> d >> m;
    vector<Job> array;
    for (int i = 0; i < m; i++) {
        int p;
        cin >> p;
        array.emplace_back(p - 1, i + 1);
    }

    sort(array.begin(), array.end());

    int l = 1, r = m;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (work(mid, d, array))
            r = mid - 1;
        else
            l = mid + 1;
    }

    cout << l << "\n";

    int batches = (m + l - 1) / l;
    int day = 0;

    for (int i = 0; i < batches; i++) {
        int start = i * l;
        int end = min(start + l, m);
        for (int j = start; j < end; j++)
            cout << array[j].index << " ";
        cout << "0\n";
        day++;
    }

    while (day < n) {
        cout << "0\n";
        day++;
    }
}

• Subtask 1: 55 / 100