oj.uz

Submission #447238

# Submission time Handle Problem Language Result Execution time Memory
447238 2021-07-25T10:29:06 Z erke Job Scheduling (CEOI12_jobs) C++11
95 / 100
 480 ms 34556 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) {
  deque<pair<int,int>> a = dq;
  res.clear();
  res.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= x; j++) {
      int t = a.front().first;
      if (t > i) break;
      if (t + d >= i) {
        res[i].push_back(a.front().second);
        a.pop_front();
      }
      else return false;
      if (a.empty()) return true;
    }
  }
}

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 = 1000000, ans = -1;
  vector<vector<int>> sav;
  while (l <= r) {
    int m = (l + r) / 2;
    if (check(m)) {
      ans = m;
      sav = res;
      r = m - 1;
    }
    else l = m + 1;
  }
  cout << ans << '\n';
  for (int i = 1; i <= n; i++) {
    for (auto &j : sav[i]) cout << j << ' ';
    cout << 0 << '\n';
  }
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:9:28: warning: control reaches end of non-void function [-Wreturn-type]
    9 |   deque<pair<int,int>> a = dq;
      |                            ^~

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4676 KB Output is correct
2 Correct 42 ms 4624 KB Output is correct
3 Correct 41 ms 4676 KB Output is correct
4 Correct 40 ms 4636 KB Output is correct
5 Correct 41 ms 4728 KB Output is correct
6 Correct 42 ms 4632 KB Output is correct
7 Correct 41 ms 4676 KB Output is correct
8 Correct 41 ms 4668 KB Output is correct
9 Correct 70 ms 8676 KB Output is correct
10 Correct 69 ms 8804 KB Output is correct
11 Correct 53 ms 3980 KB Output is correct
12 Correct 108 ms 7532 KB Output is correct
13 Correct 152 ms 11068 KB Output is correct
14 Correct 249 ms 14880 KB Output is correct
15 Correct 256 ms 17300 KB Output is correct
16 Correct 385 ms 21280 KB Output is correct
17 Correct 462 ms 26784 KB Output is correct
18 Correct 406 ms 27100 KB Output is correct
19 Runtime error 480 ms 34556 KB Memory limit exceeded
20 Correct 465 ms 26796 KB Output is correct