제출 #1258235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258235		hawashra	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	663 ms	20196 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;

  vii jobs(m);
  for (int i = 0; i < m; ++i) {
    cin >> jobs[i].first;
    jobs[i].second = i + 1;
  }
  sort(ALL(jobs));

  vector<vi> dist(n + 1);

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

    priority_queue<int, vi, greater<int>> pq;
    for (int i = 0; i < machines; ++i) pq.push(1);

    for (auto [a, id] : jobs) {
      auto t = pq.top(); pq.pop();
      if (t > a + d) return false;
      int s = max(t, a);
      if (fill){
        // schedule on day s
        dist[s].push_back(id);
      }
      // update machine: next free becomes s + 1
      pq.push(s + 1);
    }
    return true;
  };

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

  feasible_and_fill(ans, true);

  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: 100 / 100