Submission #916905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
916905	2024-01-26T18:22:43 Z	papercut	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	277 ms	29944 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	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