oj.uz

답안 #752756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752756 2023-06-03T16:41:54 Z Mo_Huzaifa Job Scheduling (CEOI12_jobs) C++14
80 / 100
 541 ms 40668 KB 
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
i64 const &N_ = 1e5 + 500; 
i64 const &M_ = 1e6 + 500;

i64 N, D, M;
vector < i64 > arr_M(M_);
vector < i64 > ans[N_];
vector < pair < i64, i64 >> DAYS;

bool check(i64 machine) {
    i64 d = 0;
    i64 cnt = 0;
    for (i64 i = 0; i < (i64) DAYS.size(); ) {
        i64 j = i;
        bool ok = false;
        i64 val = max(DAYS[i].first, d + 1);
        for (i64 cnt_ = 0; j < M and DAYS[j].first < val + 1 and DAYS[j].first >= val - D and cnt_ < machine; ++ cnt_, ++ j) {
            // Let it be
            cnt ++;
            ok = true;
        }
        if (! ok) return false;
        i = j;
        d = val;
    }
    return cnt == M;
}

void get_ans(i64 machine) {
    i64 d = 0;
    for (i64 i = 0; i < (i64) DAYS.size(); ) {
        i64 j = i;
        bool ok = false;
        i64 val = max(DAYS[i].first, d + 1);
        for (i64 cnt_ = 0; j < M and DAYS[j].first < val + 1 and DAYS[j].first >= val - D and cnt_ < machine; ++ cnt_, ++ j) {
            // Let it be
            ans[val].push_back(DAYS[j].second);
            ok = true;
        }
        if (! ok) return ;
        i = j;
        d = val;
    }
}

void Solution() {
    cin >> N >> D >> M;
    for (i64 i = 0; i < M; ++ i) {
        cin >> arr_M[i];
        DAYS.push_back(make_pair(arr_M[i], i + 1));
    }

    i64 save = -1;
    sort(DAYS.begin(), DAYS.end());

    i64 l = 0, r = M;
    while (l < r + 1) {
        i64 mid = (l + r) / 2;
        if (check(mid)) save = mid, r = mid - 1;
        else l = mid + 1;
    }

    get_ans(save);
    cout << save << endl;
    for (i64 i = 1; i < N + 1; ++ i) {
        for (auto it : ans[i]) {
            cout << it << ' ';
        }
        cout << '0' << endl;
    }
}

int main() {
    Solution();
    return 0;
}

Subtask #1
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 14268 KB Output is correct
2 Correct 50 ms 14216 KB Output is correct
3 Correct 59 ms 14152 KB Output is correct
4 Correct 50 ms 14268 KB Output is correct
5 Correct 46 ms 14268 KB Output is correct
6 Correct 48 ms 14260 KB Output is correct
7 Correct 44 ms 14280 KB Output is correct
8 Correct 46 ms 14268 KB Output is correct
9 Correct 151 ms 14116 KB Output is correct
10 Correct 153 ms 13984 KB Output is correct
11 Correct 44 ms 14012 KB Output is correct
12 Correct 90 ms 17452 KB Output is correct
13 Correct 137 ms 21956 KB Output is correct
14 Correct 207 ms 25672 KB Output is correct
15 Correct 227 ms 26964 KB Output is correct
16 Correct 326 ms 30600 KB Output is correct
17 Runtime error 353 ms 38012 KB Memory limit exceeded
18 Runtime error 364 ms 38312 KB Memory limit exceeded
19 Runtime error 541 ms 40668 KB Memory limit exceeded
20 Runtime error 334 ms 37760 KB Memory limit exceeded