Submission #480672

#	Time	Username	Problem	Language	Result	Execution time	Memory
480672		Olympia	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	1099 ms	28024 KiB

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;
map<int, 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;
    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 (stderr)

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: 95 / 100