Submission #1258232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258232		hawashra	Job Scheduling (CEOI12_jobs)	C++20	80 / 100	1097 ms	34964 KiB

jobs

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

#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define ALL(x) begin(x), end(x)

void solve() {
  int n, d, m; 
  cin >> n >> d >> m;

  // jobs[i] = {availability_day, job_id}
  vii jobs(m);
  for (int i = 0; i < m; ++i) {
    cin >> jobs[i].first;
    jobs[i].second = i + 1; // 1-based job id for printing
  }
  sort(ALL(jobs)); // by availability then id

  // dist[day] = list of job ids scheduled on that day (1..n)
  vector<vi> dist(n + 1);

  auto feasible_and_fill = [&](int machines) -> bool {
    for (int i = 0; i <= n; ++i) dist[i].clear();

    // multiset of "next free day" for each machine. Initially all are free on day 1 (i.e., next_free = 1)
    multiset<int> next_free;
    for (int i = 0; i < machines; ++i) next_free.insert(1);

    for (auto [a, id] : jobs) {

      auto it = next_free.begin();
      int t = *it;
      if (t > a + d) return false;
      int s = max(t, a);
      // schedule on day s
      dist[s].push_back(id);

      // update machine: next free becomes s + 1
      next_free.erase(it);
      next_free.insert(s + 1);
    }
    return true;
  };

  int l = 1, r = m, ans = m;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (feasible_and_fill(mid)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }

  // Recompute schedule for the minimal ans so dist matches what we print
  feasible_and_fill(ans);

  cout << ans << '\n';
  for (int day = 1; day <= n; ++day) {
    for (int id : dist[day]) cout << id << ' ';
    cout << "0\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt = 1;
  while (tt--) solve();
}

• Subtask 1: 80 / 100