Submission #480679

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480679	2021-10-17T15:53:41 Z	Olympia	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	521 ms	22856 KB

jobs

/*
 * 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

#	Verdict	Execution time	Memory	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