oj.uz

Submission #959552

# Submission time Handle Problem Language Result Execution time Memory
959552 2024-04-08T12:33:45 Z Blagoj Job Scheduling (CEOI12_jobs) C++17
0 / 100
 396 ms 21704 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 << endl;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 3344 KB Unexpected end of file - int32 expected
2 Incorrect 32 ms 3100 KB Unexpected end of file - int32 expected
3 Incorrect 32 ms 3100 KB Unexpected end of file - int32 expected
4 Incorrect 32 ms 3100 KB Unexpected end of file - int32 expected
5 Incorrect 31 ms 3088 KB Unexpected end of file - int32 expected
6 Incorrect 32 ms 3116 KB Unexpected end of file - int32 expected
7 Incorrect 32 ms 3100 KB Unexpected end of file - int32 expected
8 Incorrect 32 ms 3104 KB Unexpected end of file - int32 expected
9 Incorrect 132 ms 3616 KB Unexpected end of file - int32 expected
10 Incorrect 131 ms 3600 KB Unexpected end of file - int32 expected
11 Incorrect 27 ms 2524 KB Unexpected end of file - int32 expected
12 Incorrect 55 ms 5020 KB Unexpected end of file - int32 expected
13 Incorrect 86 ms 7204 KB Unexpected end of file - int32 expected
14 Incorrect 132 ms 9832 KB Unexpected end of file - int32 expected
15 Incorrect 133 ms 11744 KB Unexpected end of file - int32 expected
16 Incorrect 178 ms 15504 KB Unexpected end of file - int32 expected
17 Incorrect 220 ms 16328 KB Unexpected end of file - int32 expected
18 Incorrect 246 ms 18588 KB Unexpected end of file - int32 expected
19 Incorrect 396 ms 21704 KB Unexpected end of file - int32 expected
20 Incorrect 237 ms 16580 KB Unexpected end of file - int32 expected