oj.uz

Submission #959550

# Submission time Handle Problem Language Result Execution time Memory
959550 2024-04-08T12:31:54 Z Blagoj Job Scheduling (CEOI12_jobs) C++17
0 / 100
 290 ms 25256 KB 
#include <bits/stdc++.h>
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
using namespace std;
 
#define endl '\n'
#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) {
        cout << x << " ";
        if (x == 0) cout << endl;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3532 KB Expected EOLN
2 Incorrect 22 ms 3516 KB Expected EOLN
3 Incorrect 27 ms 3352 KB Expected EOLN
4 Incorrect 26 ms 3600 KB Expected EOLN
5 Incorrect 22 ms 3604 KB Expected EOLN
6 Incorrect 22 ms 3568 KB Expected EOLN
7 Incorrect 22 ms 3356 KB Expected EOLN
8 Incorrect 22 ms 3528 KB Expected EOLN
9 Incorrect 39 ms 4040 KB Expected EOLN
10 Incorrect 36 ms 4028 KB Expected EOLN
11 Incorrect 30 ms 3024 KB Expected EOLN
12 Incorrect 65 ms 5840 KB Expected EOLN
13 Incorrect 81 ms 8396 KB Expected EOLN
14 Incorrect 113 ms 11752 KB Expected EOLN
15 Incorrect 134 ms 13508 KB Expected EOLN
16 Incorrect 177 ms 17408 KB Expected EOLN
17 Incorrect 201 ms 20420 KB Expected EOLN
18 Incorrect 248 ms 21784 KB Expected EOLN
19 Incorrect 290 ms 25256 KB Expected EOLN
20 Incorrect 213 ms 20164 KB Expected EOLN