Submission #679819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
679819	2023-01-09T10:21:24 Z	peijar	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	403 ms	21560 KB

jobs

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbJours, nbTravaux, deadline;
  cin >> nbJours >> deadline >> nbTravaux;

  vector<int> debut(nbTravaux);
  for (int &x : debut) {
    cin >> x;
    --x;
  }
  vector<int> order(nbTravaux);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(),
       [&](int i, int j) { return debut[i] < debut[j]; });

  auto check = [&](int nbMachines) -> bool {
    queue<int> dispo;
    for (int i = 0; i < nbJours; ++i)
      dispo.push(i);
    vector<int> surTemps(nbJours);
    for (int i : order) {
      int t = debut[i];
      while (!dispo.empty() and dispo.front() < t)
        dispo.pop();
      if (dispo.empty() or dispo.front() > t + deadline)
        return false;

      int tt = dispo.front();
      if (tt > t + deadline)
        return false;
      surTemps[tt]++;
      if (surTemps[tt] == nbMachines)
        dispo.pop();
    }
    return true;
  };

  int lo = 1, up = nbTravaux;
  while (lo < up) {
    int mid = (lo + up) / 2;
    if (check(mid))
      up = mid;
    else
      lo = mid + 1;
  }
  cout << lo << endl;
  int curJour = 0;
  vector<int> onDay;
  vector<int> surTemps(nbJours);
  for (int i : order) {
    int t = debut[i];
    while (curJour < t or surTemps[curJour] == lo) {
      for (int x : onDay)
        cout << x << ' ';
      cout << 0 << '\n';
      onDay.clear();
      curJour++;
    }
    assert(curJour < nbJours and curJour <= t + deadline);
    onDay.push_back(i + 1);
    surTemps[curJour]++;
  }
  while (curJour < nbJours) {
    for (int x : onDay)
      cout << x << ' ';
    cout << 0 << '\n';
    onDay.clear();
    curJour++;
  }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3076 KB	Output is correct
2	Correct	21 ms	3248 KB	Output is correct
3	Correct	22 ms	3056 KB	Output is correct
4	Correct	24 ms	2996 KB	Output is correct
5	Correct	22 ms	3088 KB	Output is correct
6	Correct	25 ms	3040 KB	Output is correct
7	Correct	24 ms	3124 KB	Output is correct
8	Correct	26 ms	3044 KB	Output is correct
9	Correct	46 ms	3508 KB	Output is correct
10	Correct	47 ms	3540 KB	Output is correct
11	Correct	28 ms	2452 KB	Output is correct
12	Correct	58 ms	4740 KB	Output is correct
13	Correct	85 ms	6992 KB	Output is correct
14	Correct	125 ms	9432 KB	Output is correct
15	Correct	146 ms	11564 KB	Output is correct
16	Correct	192 ms	13928 KB	Output is correct
17	Correct	284 ms	16292 KB	Output is correct
18	Correct	316 ms	18520 KB	Output is correct
19	Correct	403 ms	21560 KB	Output is correct
20	Correct	237 ms	16208 KB	Output is correct