oj.uz

답안 #556847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556847 2022-05-04T06:23:20 Z Jomnoi Job Scheduling (CEOI12_jobs) C++17
100 / 100
 212 ms 13840 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_M = 1e6 + 10;

int N, D, M;
int S[MAX_M], id[MAX_M];

bool solve(int mid) {
    int i = 1;
    for(int days = 1; days <= N and i <= M; days++) {
        if(days > S[id[i]] + D) {
            break;
        }

        int cnt = mid;
        while(i <= M and S[id[i]] <= days and cnt--) {
            i++;
        }
    }
    return i == M + 1;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> N >> D >> M;
    for(int i = 1; i <= M; i++) {
        cin >> S[i];
        id[i] = i;
    }

    sort(id + 1, id + M + 1, [&](const int &a, const int &b) {
        return S[a] < S[b];
    });

    int l = 1, r = M, ans = -1;
    while(l <= r) {
        int mid = (l + r) / 2;

        if(solve(mid) == true) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }

    cout << ans << '\n';
    for(int i = 1, j = 1; i <= N; i++) {
        for(int k = 0; j <= M and k < ans; j++, k++) {
            cout << id[j] << ' ';
        }
        cout << "0\n";
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 1620 KB Output is correct
2 Correct 17 ms 1748 KB Output is correct
3 Correct 16 ms 1648 KB Output is correct
4 Correct 18 ms 1684 KB Output is correct
5 Correct 16 ms 1748 KB Output is correct
6 Correct 17 ms 1688 KB Output is correct
7 Correct 16 ms 1740 KB Output is correct
8 Correct 17 ms 1620 KB Output is correct
9 Correct 21 ms 1892 KB Output is correct
10 Correct 20 ms 1916 KB Output is correct
11 Correct 23 ms 1740 KB Output is correct
12 Correct 48 ms 3180 KB Output is correct
13 Correct 67 ms 4600 KB Output is correct
14 Correct 100 ms 6100 KB Output is correct
15 Correct 113 ms 7560 KB Output is correct
16 Correct 151 ms 9108 KB Output is correct
17 Correct 177 ms 10604 KB Output is correct
18 Correct 189 ms 12052 KB Output is correct
19 Correct 212 ms 13840 KB Output is correct
20 Correct 181 ms 10572 KB Output is correct