oj.uz

Submission #959553

# Submission time Handle Problem Language Result Execution time Memory
959553 2024-04-08T12:34:46 Z Blagoj Job Scheduling (CEOI12_jobs) C++17
100 / 100
 408 ms 23916 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define all(x) x.begin(), x.end()
 
int n, d, m;
vector<pair<int, int>> v;
vector<int> cur;
 
bool check(int x) {
    queue<pair<int, int>> q;
    int cnt = 0;
    cur.clear();
    for (int day = 1; day <= n; day++) {
        if (q.size() && day - q.front().first > d) return 0;
        while (cnt < m && v[cnt].first == day) q.push(v[cnt++]);
        for (int i = 0; i < x && q.size(); i++) {
            cur.push_back(q.front().second);
            q.pop();
        }
        cur.push_back(0);
    }
    return (q.size() == 0);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> d >> m;
    v.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> v[i].first;
        v[i].second = i + 1;
    }
    sort(all(v));
    int l = 0, r = m;
    vector<int> ans;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
            ans = cur;
        }
        else l = mid;
    }
    cout << r << endl;
    for (auto x : ans) {
        if (x != 0) cout << x << " ";
        else cout << 0 << endl;
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3096 KB Output is correct
2 Correct 33 ms 3092 KB Output is correct
3 Correct 33 ms 3256 KB Output is correct
4 Correct 32 ms 3100 KB Output is correct
5 Correct 32 ms 3180 KB Output is correct
6 Correct 36 ms 3088 KB Output is correct
7 Correct 38 ms 3068 KB Output is correct
8 Correct 34 ms 3208 KB Output is correct
9 Correct 151 ms 3668 KB Output is correct
10 Correct 153 ms 3632 KB Output is correct
11 Correct 30 ms 2668 KB Output is correct
12 Correct 56 ms 5068 KB Output is correct
13 Correct 85 ms 7272 KB Output is correct
14 Correct 125 ms 9676 KB Output is correct
15 Correct 153 ms 11716 KB Output is correct
16 Correct 180 ms 14764 KB Output is correct
17 Correct 234 ms 16404 KB Output is correct
18 Correct 270 ms 20500 KB Output is correct
19 Correct 408 ms 23916 KB Output is correct
20 Correct 224 ms 18520 KB Output is correct