Submission #497294

#	Time	Username	Problem	Language	Result	Execution time	Memory
497294		dutinmeow	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	377 ms	23980 KiB

jobs

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

using pii = pair<long long, long long>;

long long N, D, M;
pii A[1000005];

bool check(long long m) {
    for (int i = 1, j = 0; i <= N && j < M; i++) 
        for (int k = 0; k < m && j < M && A[j].first <= i; k++, j++) 
            if (i - A[j].first > D) 
                return 0;
    return 1;
}

int main() {
    cin >> N >> D >> M;
    for (int i = 0; i < M; i++) {
        int a; cin >> a;
        A[i] = {a, i + 1};
    }
    sort(A, A + M);

    long long l = 0, r = M;
    while (l < r) {
        long long m = (l + r) / 2;
        if (check(m))
            r = m;
        else 
            l = m + 1;
    }

    cout << l << '\n';
    for (int i = 1, j = 0; i <= N && j < M; i++) {
        for (int k = 0; k < l && j < M && A[j].first <= i; k++, j++) 
            cout << A[j].second << ' ';
        cout << 0 << '\n';
    }
}

• Subtask 1: 15 / 100