oj.uz

Submission #507571

# Submission time Handle Problem Language Result Execution time Memory
507571 2022-01-12T18:29:12 Z Christopher_ Job Scheduling (CEOI12_jobs) C++17
100 / 100
 238 ms 14020 KB 
/**
 *    author:  lani
 *    created: 12.01.2022 20:57:54
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "debug.hpp"
#else
  #define dbg(...) void(37)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, d, m;
  cin >> n >> d >> m;
  vector<pair<int,int>> a(m);
  for (int i = 0; i < m; ++i) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(a.begin(), a.end());
  auto Check = [&](int k) {
    int day = 1, work = 0;
    for (int i = 0; i < m; ++i) {
      if (a[i].first > day) {
        day = a[i].first;
        work = 1;
      } else if (a[i].first + d < day) {
        return false;
      } else {
        ++work;
      }
      if (work >= k) {
        work = 0;
        ++day;
      }
    }
    return true;
  };
  int ans = (int) 1e7;
  int low = 0, high = (int) 1e7;
  while (low <= high) {
    int mid = (low + high) >> 1;
    if (Check(mid)) {
      high = mid - 1;
      ans = mid;
    } else {
      low = mid + 1;
    }
  }
  cout << ans << '\n';
  dbg();
  int work = 0;
  for (int i = 0; i < n; ++i) {
    int cnt = 0;
    while (work < m && cnt < ans && a[work].first <= i + 1) {
      cout << a[work].second + 1 << ' ';
      ++work;
      ++cnt;
    }
    cout << "0\n";
  }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1620 KB Output is correct
2 Correct 18 ms 1640 KB Output is correct
3 Correct 19 ms 1628 KB Output is correct
4 Correct 18 ms 1612 KB Output is correct
5 Correct 19 ms 1708 KB Output is correct
6 Correct 18 ms 1624 KB Output is correct
7 Correct 18 ms 1612 KB Output is correct
8 Correct 18 ms 1628 KB Output is correct
9 Correct 26 ms 1872 KB Output is correct
10 Correct 27 ms 1860 KB Output is correct
11 Correct 24 ms 1628 KB Output is correct
12 Correct 50 ms 3164 KB Output is correct
13 Correct 79 ms 4584 KB Output is correct
14 Correct 107 ms 6032 KB Output is correct
15 Correct 133 ms 7616 KB Output is correct
16 Correct 160 ms 9108 KB Output is correct
17 Correct 196 ms 10532 KB Output is correct
18 Correct 204 ms 12100 KB Output is correct
19 Correct 238 ms 14020 KB Output is correct
20 Correct 188 ms 10524 KB Output is correct