oj.uz

Submission #447239

# Submission time Handle Problem Language Result Execution time Memory
447239 2021-07-25T10:34:37 Z erke Job Scheduling (CEOI12_jobs) C++11
100 / 100
 440 ms 27204 KB 
#include <bits/stdc++.h>
using namespace std;

int n, d, m;
deque<pair<int,int>> dq;
vector<vector<int>> res;

bool check(int x) {
  res.assign(n + 1, vector<int>());
  int p = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= x; j++) {
      int t = dq[p].first;
      if (t > i) break;
      if (t + d >= i) {
        res[i].push_back(dq[p].second);
        p++;
      }
      else return false;
      if (p == m) return true;
    }
  }
  return false;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> d >> m;
  dq.resize(m);
  for (int i = 0; i < m; i++) {
    cin >> dq[i].first;
    dq[i].second = i + 1;
  }
  sort(dq.begin(), dq.end());
  int l = 1, r = m, ans = -1;
  vector<vector<int>> sav;
  while (l <= r) {
    int x = (l + r) / 2;
    if (check(x)) {
      ans = x;
      sav = res;
      r = x - 1;
    }
    else l = x + 1;
  }
  cout << ans << '\n';
  for (int i = 1; i <= n; i++) {
    for (auto &j : sav[i]) cout << j << ' ';
    cout << 0 << '\n';
  }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3144 KB Output is correct
2 Correct 33 ms 3040 KB Output is correct
3 Correct 34 ms 3040 KB Output is correct
4 Correct 33 ms 3144 KB Output is correct
5 Correct 35 ms 3008 KB Output is correct
6 Correct 33 ms 3044 KB Output is correct
7 Correct 33 ms 3092 KB Output is correct
8 Correct 35 ms 3040 KB Output is correct
9 Correct 64 ms 7524 KB Output is correct
10 Correct 62 ms 7528 KB Output is correct
11 Correct 42 ms 2760 KB Output is correct
12 Correct 89 ms 5308 KB Output is correct
13 Correct 134 ms 8288 KB Output is correct
14 Correct 186 ms 11632 KB Output is correct
15 Correct 237 ms 12976 KB Output is correct
16 Correct 288 ms 16196 KB Output is correct
17 Correct 362 ms 20516 KB Output is correct
18 Correct 397 ms 20868 KB Output is correct
19 Correct 440 ms 27204 KB Output is correct
20 Correct 347 ms 20452 KB Output is correct