oj.uz

Submission #730012

# Submission time Handle Problem Language Result Execution time Memory
730012 2023-04-25T05:12:21 Z eysbutno Job Scheduling (CEOI12_jobs) C++11
100 / 100
 384 ms 17056 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int main() {
    int n, d, m; cin >> n >> d >> m;
    vector<pair<int, int>> reqs(m);
    for (int i = 0; i < m; i++) {
        cin >> reqs[i].f;
        reqs[i].s = i + 1;
    }
    sort(begin(reqs), end(reqs));
    auto check = [&](int mid) {
        int num = 0;
        for (int i = 1; i <= n; i++) { // day
            for (int j = 0; j < mid; j++) { // adding
                if (i - reqs[num].f > d) return false;
                if (reqs[num].f > i) break;
                num++;
                if (num == m) return true;
            }
        }
        return false;
    };
    int low = 1, high = m;
    while (low < high) {
        int mid = (low + high) / 2;
        if (check(mid)) high = mid;
        else low = mid + 1;
    }
    cout << low << "\n";
    int num = 0;
    for (int i = 1; i <= n; i++) { // day
        bool added = false;
        for (int j = 0; j < low; j++) { // adding
            if (num == m) break;
            if (i - reqs[num].f > d) return false;
            if (reqs[num].f > i) break;
            cout << reqs[num].s << " ";
            num++;
        }
        cout << 0 << "\n";
    }
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:34:14: warning: unused variable 'added' [-Wunused-variable]
   34 |         bool added = false;
      |              ^~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1968 KB Output is correct
2 Correct 30 ms 1900 KB Output is correct
3 Correct 43 ms 1904 KB Output is correct
4 Correct 29 ms 1884 KB Output is correct
5 Correct 36 ms 1868 KB Output is correct
6 Correct 30 ms 1932 KB Output is correct
7 Correct 33 ms 1976 KB Output is correct
8 Correct 32 ms 1896 KB Output is correct
9 Correct 45 ms 2108 KB Output is correct
10 Correct 43 ms 2024 KB Output is correct
11 Correct 40 ms 1964 KB Output is correct
12 Correct 81 ms 3896 KB Output is correct
13 Correct 116 ms 5692 KB Output is correct
14 Correct 170 ms 8012 KB Output is correct
15 Correct 207 ms 9424 KB Output is correct
16 Correct 261 ms 11960 KB Output is correct
17 Correct 348 ms 13824 KB Output is correct
18 Correct 322 ms 15060 KB Output is correct
19 Correct 384 ms 17056 KB Output is correct
20 Correct 302 ms 13900 KB Output is correct