답안 #851774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851774 2023-09-20T15:02:24 Z nhphucqt Job Scheduling (CEOI12_jobs) C++17
100 / 100
251 ms 23684 KB
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+7;
const int DAY = 1e5+7;
int numDay, delay, numTask;
pair<int, int> beg[N];
vector<int> res[DAY];

bool isOk(int numWorker, bool isTrace = false) {
    queue<pair<int,int>> q;
    for (int i = 1, j = 1; i <= numDay; ++i) {
        while (j <= numTask && beg[j].first == i) {
            q.emplace(beg[j].first+delay, beg[j].second);
            j++;
        }
        if (!q.empty() && q.front().first < i) {
            return false;
        }
        int cnt = 0;
        while (!q.empty() && ++cnt <= numWorker) {
            if (isTrace) {
                res[i].push_back(q.front().second);
            }
            q.pop();
        }
    }
    return true;
}

int solve() {
    int l = 1;
    int r = numTask;
    while (l < r) {
        int m = l+r>>1;
        if (isOk(m)) {
            r = m;
        } else {
            l = m+1;
        }
    }
    return l;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    #ifdef NHPHUCQT
    freopen("demo.inp", "r", stdin);
    freopen("demo.out", "w", stdout);
    #endif

    cin >> numDay >> delay >> numTask;
    for (int i = 1; i <= numTask; ++i) {
        cin >> beg[i].first;
        beg[i].second = i;
    }

    sort(beg+1,beg+numTask+1);

    // for (int i = 1; i <= numTask; ++i) {
    //     cerr << beg[i].first << ' ';
    // }
    // cerr << '\n';

    int num = solve();
    isOk(num, true);

    cout << num << '\n';
    for (int i = 1; i <= numDay; ++i) {
        for (int x : res[i]) {
            cout << x << ' ';
        }
        cout << 0 << '\n';
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int solve()':
jobs.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int m = l+r>>1;
      |                 ~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 6992 KB Output is correct
2 Correct 23 ms 6992 KB Output is correct
3 Correct 21 ms 6744 KB Output is correct
4 Correct 24 ms 6736 KB Output is correct
5 Correct 22 ms 6744 KB Output is correct
6 Correct 22 ms 6900 KB Output is correct
7 Correct 21 ms 7000 KB Output is correct
8 Correct 22 ms 6992 KB Output is correct
9 Correct 31 ms 6224 KB Output is correct
10 Correct 31 ms 6268 KB Output is correct
11 Correct 25 ms 5968 KB Output is correct
12 Correct 55 ms 8020 KB Output is correct
13 Correct 76 ms 11856 KB Output is correct
14 Correct 107 ms 14028 KB Output is correct
15 Correct 128 ms 13904 KB Output is correct
16 Correct 153 ms 18508 KB Output is correct
17 Correct 185 ms 21968 KB Output is correct
18 Correct 212 ms 21740 KB Output is correct
19 Correct 251 ms 23684 KB Output is correct
20 Correct 183 ms 21912 KB Output is correct