oj.uz

답안 #480679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480679 2021-10-17T15:53:41 Z Olympia Job Scheduling (CEOI12_jobs) C++17
100 / 100
 521 ms 22856 KB 
/*
 * 8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <map>
#include <queue>

using namespace std;
int N, D, M;
vector<vector<int>> myMap;
vector<int> days;
pair<bool, vector<vector<int>>> valid (int machines) {
    queue<pair<int,int>> q;
    vector<vector<int>> ans;
    for (int i = 1; i <= N; i++) {
        int k = machines;
        ans.push_back((vector<int>){});
        for (int j = 0; j < myMap[i].size(); j++) {
            q.push({i, myMap[i][j]});
        }
        while(k--) {
            if (q.empty()) {
                break;
            }
            if (i - q.front().first > D) {
                return {false, {}};
            }
            ans.back().push_back(q.front().second + 1);
            q.pop();
        }
    }
    if (!q.empty()) return {false, {}};
    return {true, ans};
}
int binSearch (int l, int r) {
    int m = (l + r)/2;
    if (l == r) {
        return l;
    }
    if (valid(m).first) {
        return binSearch(l, m);
    } else {
        return binSearch(m + 1, r);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> D >> M;
    myMap.resize(N + 1);
    for (int i = 0; i < M; i++) {
        int x;
        cin >> x;
        days.push_back(x);
        myMap[x].push_back(i);
    }
    cout << binSearch(0, M) << endl;
    auto p = valid (2);
    vector<vector<int>> ans = p.second;
    for (int i = 0; i < N; i++) {
        if (i >= (int)ans.size()) {
            cout << 0;
            if (i != N) cout << endl;
            continue;
        }
        for (int j: ans[i]) {
            cout << j << " ";
        }
        cout << 0;
        if (i != N) cout << endl;
    }
}

Compilation message

jobs.cpp: In function 'std::pair<bool, std::vector<std::vector<int> > > valid(int)':
jobs.cpp:24:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int j = 0; j < myMap[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 3008 KB Output is correct
2 Correct 42 ms 3008 KB Output is correct
3 Correct 51 ms 2964 KB Output is correct
4 Correct 43 ms 3008 KB Output is correct
5 Correct 42 ms 3016 KB Output is correct
6 Correct 39 ms 2972 KB Output is correct
7 Correct 50 ms 3008 KB Output is correct
8 Correct 44 ms 3008 KB Output is correct
9 Correct 201 ms 9632 KB Output is correct
10 Correct 198 ms 9880 KB Output is correct
11 Correct 33 ms 2372 KB Output is correct
12 Correct 61 ms 4196 KB Output is correct
13 Correct 114 ms 7028 KB Output is correct
14 Correct 221 ms 9644 KB Output is correct
15 Correct 169 ms 9800 KB Output is correct
16 Correct 269 ms 12928 KB Output is correct
17 Correct 324 ms 16760 KB Output is correct
18 Correct 312 ms 15780 KB Output is correct
19 Correct 521 ms 22856 KB Output is correct
20 Correct 323 ms 16724 KB Output is correct