제출 #1312007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312007		quacksire	Job Scheduling (CEOI12_jobs)	C++20	10 / 100	120 ms	13632 KiB

jobs

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

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

// Check if num workers can complete jobs with distance d
bool work(int num, int d, vector<Job> &array) {
    int m = array.size();
    for (int i = 0; i < m / num; 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";

    for (int i = 0; i < m; i++) {
        cout << array[i].index << " ";
        if ((i + 1) % l == 0)
            cout << "0\n";
    }

    return 0;
}

• Subtask 1: 10 / 100