Submission #480677

#	Time	Username	Problem	Language	Result	Execution time	Memory
480677		Olympia	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	1099 ms	22152 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;
vector<vector<int>> ans;
bool valid (int machines) {
    queue<pair<int,int>> q;
    ans.clear();
    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();
        }
    }
    return q.empty();
}
int binSearch (int l, int r) {
    int m = (l + r)/2;
    if (l == r) {
        return l;
    }
    if (valid(m)) {
        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);
    }
    valid (binSearch(0, M));
    cout << binSearch(0, M) << endl;
    for (int i = 0; i < N; i++) {
        if (i >= (int)ans.size()) {
            cout << "0\n";
            continue;
        }
        for (int j: ans[i]) {
            cout << j << " ";
        }
        cout << "0\n";
    }
}

Compilation message (stderr)

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

• Subtask 1: 75 / 100