답안 #916905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916905 2024-01-26T18:22:43 Z papercut Job Scheduling (CEOI12_jobs) C++17
100 / 100
277 ms 29944 KB
#include <bits/stdc++.h>

#include <iostream>
#include <vector>

#ifdef LOCAL
#include "debug/debug.hpp"
#else
#define Debug(...) 42
#endif

namespace {

void RunCase([[maybe_unused]] int testcase) {
  int n{};
  int d{};
  int m{};
  std::cin >> n >> d >> m;

  std::vector<int> day(m);
  for (int& d : day) {
    std::cin >> d;
    --d;
  }

  std::vector<int> order(m);
  std::iota(order.begin(), order.end(), 0);
  std::sort(order.begin(), order.end(),
            [&day](int i, int j) { return day[i] < day[j]; });

  auto make_schedule =
      [&](int num_workers) -> std::optional<std::vector<std::vector<int>>> {
    std::vector result(n, std::vector<int>());
    std::queue<int> active;
    int id = 0;
    for (int i = 0; i < n; ++i) {
      while (id < m && day[order[id]] == i) {
        active.push(id++);
      }
      int processed = 0;
      while (!active.empty() && processed < num_workers) {
        int index = active.front();
        active.pop();
        if (day[order[index]] + d < i) {
          return std::nullopt;
        }
        processed += 1;
        result[i].push_back(order[index] + 1);
      }
    }
    return result;
  };

  int low = 0;
  int high = m;
  std::vector answer(n, std::vector<int>());
  while (high - low > 1) {
    int mid = (low + high) >> 1;
    if (auto schedule = make_schedule(mid); schedule.has_value()) {
      high = mid;
      answer = std::move(schedule.value());
    } else {
      low = mid;
    }
  }

  std::cout << high << "\n";
  for (int i = 0; i < n; ++i) {
    for (int id : answer[i]) {
      std::cout << id << " ";
    }
    std::cout << "0\n";
  }
}

void Main() {
  int testcases = 1;
  // std::cin >> testcases;
  for (int tt = 1; tt <= testcases; ++tt) {
    RunCase(tt);
  }
}

}  // namespace

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  Main();
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 3560 KB Output is correct
2 Correct 22 ms 3456 KB Output is correct
3 Correct 24 ms 3772 KB Output is correct
4 Correct 23 ms 3456 KB Output is correct
5 Correct 22 ms 3456 KB Output is correct
6 Correct 23 ms 3572 KB Output is correct
7 Correct 23 ms 3564 KB Output is correct
8 Correct 25 ms 3712 KB Output is correct
9 Correct 34 ms 8196 KB Output is correct
10 Correct 35 ms 8448 KB Output is correct
11 Correct 27 ms 3152 KB Output is correct
12 Correct 60 ms 6176 KB Output is correct
13 Correct 93 ms 10184 KB Output is correct
14 Correct 143 ms 13772 KB Output is correct
15 Correct 145 ms 12496 KB Output is correct
16 Correct 200 ms 19316 KB Output is correct
17 Correct 255 ms 24672 KB Output is correct
18 Correct 237 ms 23968 KB Output is correct
19 Correct 277 ms 29944 KB Output is correct
20 Correct 242 ms 24672 KB Output is correct