oj.uz

답안 #1063582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063582 2024-08-17T20:55:33 Z DeathIsAwe Job Scheduling (CEOI12_jobs) C++14
40 / 100
 233 ms 20664 KB 
#include <bits/stdc++.h>
using namespace std;


bool schedule(vector<int> requests, int n, int d, int m, int a) {
    bool ans = true;
    int counter;
    for (int i=0;i<n;i++) {
        counter = 0;
        while (counter < a && requests.size() > 0 && requests[requests.size() - 1] < i + 2) {
            counter++;
            if (requests[requests.size() - 1] > i + d + 1) {
                ans = false;
                break;
            }
            requests.pop_back();
        }
        if (!ans) {
            break;
        }
    }
    if (requests.size() > 0) {
        ans = false;
    }
    return ans;
}


int main() {
    int n, d, m; cin >> n >> d >> m;
    vector<int> requests(m);
    vector<vector<int>> requestmapper(n + 1);
    for (int i=0;i<m;i++) {
        cin >> requests[i];
        requestmapper[requests[i]].push_back(i + 1);
    }
    sort(requests.begin(), requests.end(), greater<int>());

    int top = m, bottom = 0, middle;
    while (top > bottom + 1) {
        middle = (top + bottom) / 2;
        if (schedule(requests, n, d, m, middle)) {
            top = middle;
        } else {
            bottom = middle;
        }
    }



    int counter, temp;
    cout << top << '\n';
    for (int i=0;i<n;i++) {
        counter = 0;
        while (counter < top && requests.size() > 0 && requests[requests.size() - 1] < i + 2) {
            temp = requests[requests.size() - 1];
            counter++;
            cout << requestmapper[temp][requestmapper[temp].size() - 1] << ' ';
            requestmapper[temp].pop_back();
            requests.pop_back();
        }
        cout << 0 << '\n';
    }
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 2380 KB Output isn't correct
2 Incorrect 19 ms 2380 KB Output isn't correct
3 Incorrect 19 ms 2380 KB Output isn't correct
4 Incorrect 20 ms 2380 KB Output isn't correct
5 Incorrect 20 ms 2376 KB Output isn't correct
6 Incorrect 19 ms 2380 KB Output isn't correct
7 Incorrect 19 ms 2376 KB Output isn't correct
8 Incorrect 22 ms 2376 KB Output isn't correct
9 Incorrect 27 ms 4812 KB Output isn't correct
10 Incorrect 33 ms 4816 KB Output isn't correct
11 Correct 24 ms 2256 KB Output is correct
12 Correct 49 ms 4160 KB Output is correct
13 Correct 72 ms 6844 KB Output is correct
14 Correct 120 ms 8968 KB Output is correct
15 Correct 148 ms 10568 KB Output is correct
16 Correct 174 ms 13228 KB Output is correct
17 Correct 199 ms 16028 KB Output is correct
18 Incorrect 191 ms 16912 KB Output isn't correct
19 Incorrect 233 ms 20664 KB Output isn't correct
20 Correct 201 ms 16028 KB Output is correct