oj.uz

답안 #642989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642989 2022-09-21T02:26:24 Z thinhcute Job Scheduling (CEOI12_jobs) C++17
100 / 100
 229 ms 13728 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

#define MAX 1001000

int n, d, m;
pair<int, int> a[MAX];

bool f(int mid)
{
    for (int i = 1, j = 1; i <= n && j < m; ++i) {
        int cnt = 0;
        while (j < m && cnt < mid && a[j].first <= i && a[j].first + d >= i) {
            ++cnt;
            ++j;
        } 
        if (j <= m && a[j].first + d < i) return false;
    }
    return true;
}

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

    cin >> n >> d >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].fi;
        a[i].se = i;
    }

    sort(a + 1, a + m + 1);

    int l = 1, r = m, res = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (f(mid)) {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    cout << res << endl;
    
    for (int i = 1, j = 1; i <= n; ++i) {
        int cnt = 0;
        while (j <= m && cnt < res && a[j].first <= i && a[j].first + d >= i) {
            cout << a[j].second << " ";
            ++cnt;
            ++j;
        } 
        cout << "0\n";
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 1696 KB Output is correct
2 Correct 23 ms 1600 KB Output is correct
3 Correct 18 ms 1708 KB Output is correct
4 Correct 17 ms 1728 KB Output is correct
5 Correct 16 ms 1620 KB Output is correct
6 Correct 16 ms 1636 KB Output is correct
7 Correct 16 ms 1620 KB Output is correct
8 Correct 16 ms 1620 KB Output is correct
9 Correct 26 ms 1792 KB Output is correct
10 Correct 33 ms 1876 KB Output is correct
11 Correct 23 ms 1620 KB Output is correct
12 Correct 48 ms 3124 KB Output is correct
13 Correct 76 ms 4608 KB Output is correct
14 Correct 127 ms 6160 KB Output is correct
15 Correct 120 ms 7548 KB Output is correct
16 Correct 184 ms 9108 KB Output is correct
17 Correct 179 ms 10524 KB Output is correct
18 Correct 202 ms 12020 KB Output is correct
19 Correct 229 ms 13728 KB Output is correct
20 Correct 173 ms 10572 KB Output is correct