oj.uz

Submission #638030

# Submission time Handle Problem Language Result Execution time Memory
638030 2022-09-04T10:21:58 Z SeyedAmirHs Job Scheduling (CEOI12_jobs) C++17
100 / 100
 219 ms 18576 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, d, m;
  cin >> n >> d >> m;
  vector<vector<int>> works_in_day(n);
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    x--;
    works_in_day[x].push_back(i);
  }

  auto can = [&](int y) -> bool {
    int day = 0;
    queue<int> q;
    while (day < n) {
      for (auto &x : works_in_day[day]) {
        q.push(day + d);
      }
      int cnt = 0;
      while (cnt < y and !q.empty()) {
        if (day > q.front()) {
          return false;
        }
        q.pop();
        cnt++;
      }
      day++;
    }
    return q.empty();
  };

  int l = 0, r = m;
  while (r - l > 1) {
    int mid = l + (r - l) / 2;
    if (can(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  int need = r;
  queue<int> q;
  cout << need << '\n';
  for (int i = 0; i < n; i++) {
    for (auto &x : works_in_day[i]) {
      q.push(x);
    }
    int cnt = 0;
    while (cnt < need and !q.empty()) {
      cout << q.front() + 1 << ' ';
      q.pop();
      cnt++;
    }
    cout << 0 << '\n';
  }
}

Compilation message

jobs.cpp: In lambda function:
jobs.cpp:25:18: warning: unused variable 'x' [-Wunused-variable]
   25 |       for (auto &x : works_in_day[day]) {
      |                  ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3008 KB Output is correct
2 Correct 22 ms 3064 KB Output is correct
3 Correct 26 ms 3020 KB Output is correct
4 Correct 19 ms 3052 KB Output is correct
5 Correct 19 ms 3048 KB Output is correct
6 Correct 19 ms 2984 KB Output is correct
7 Correct 21 ms 3140 KB Output is correct
8 Correct 19 ms 3016 KB Output is correct
9 Correct 30 ms 4888 KB Output is correct
10 Correct 29 ms 4904 KB Output is correct
11 Correct 19 ms 2364 KB Output is correct
12 Correct 39 ms 4440 KB Output is correct
13 Correct 60 ms 7756 KB Output is correct
14 Correct 125 ms 10564 KB Output is correct
15 Correct 95 ms 11468 KB Output is correct
16 Correct 140 ms 12508 KB Output is correct
17 Correct 159 ms 15692 KB Output is correct
18 Correct 219 ms 15032 KB Output is correct
19 Correct 188 ms 18576 KB Output is correct
20 Correct 154 ms 15588 KB Output is correct