oj.uz

Submission #973195

# Submission time Handle Problem Language Result Execution time Memory
973195 2024-05-01T15:50:08 Z njoop Job Scheduling (CEOI12_jobs) C++17
100 / 100
 145 ms 13652 KB 
#include <bits/stdc++.h>

using namespace std;

int n, d, m, in, l=0, r=1e9, mid;
vector<int> t[100010];

bool solve(int num) {
    queue<int> q;
    for(int i=1; i<=n; i++) {
        for(int j: t[i]) q.push(i);
        for(int j=1; j<=num && !q.empty(); j++) q.pop();
        if(!q.empty() && i-q.front() >= d) {
            return 0;
        }
    }
    return 1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d >> m;
    for(int i=1; i<=m; i++) {
        cin >> in;
        t[in].push_back(i);
    }
    while(l < r) {
        mid = (l+r)>>1;
        if(solve(mid)) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    cout << l << "\n";
    queue<int> q;
    for(int i=1; i<=n; i++) {
        for(int j: t[i]) q.push(j);
        for(int j=1; j<=l && !q.empty(); j++) {
            cout << q.front() << " ";
            q.pop();
        }
        cout << "0\n";
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'bool solve(int)':
jobs.cpp:11:17: warning: unused variable 'j' [-Wunused-variable]
   11 |         for(int j: t[i]) q.push(i);
      |                 ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4056 KB Output is correct
2 Correct 18 ms 4060 KB Output is correct
3 Correct 17 ms 4060 KB Output is correct
4 Correct 18 ms 4060 KB Output is correct
5 Correct 18 ms 4056 KB Output is correct
6 Correct 19 ms 4316 KB Output is correct
7 Correct 17 ms 4060 KB Output is correct
8 Correct 21 ms 4108 KB Output is correct
9 Correct 24 ms 4184 KB Output is correct
10 Correct 26 ms 4188 KB Output is correct
11 Correct 17 ms 3928 KB Output is correct
12 Correct 33 ms 4956 KB Output is correct
13 Correct 50 ms 6992 KB Output is correct
14 Correct 79 ms 8272 KB Output is correct
15 Correct 83 ms 9004 KB Output is correct
16 Correct 118 ms 10832 KB Output is correct
17 Correct 130 ms 12616 KB Output is correct
18 Correct 125 ms 12664 KB Output is correct
19 Correct 145 ms 13652 KB Output is correct
20 Correct 131 ms 12812 KB Output is correct