Submission #916905

#	Time	Username	Problem	Language	Result	Execution time	Memory
916905		papercut	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	277 ms	29944 KiB

jobs

#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;
}

• Subtask 1: 100 / 100