Submission #999554

#	Time	Username	Problem	Language	Result	Execution time	Memory
999554		m_bezrutchka	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	307 ms	23628 KiB

jobs

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

const int MAXN = 1e5 + 10;

int n, d, m;
vector <int> requests[MAXN];
vector <int> resp[MAXN];

bool possible(int k) {
  // printf("possible %d\n", k);
  if (k <= 0) return false;
  if (k >= m) return true;
  for (int day = 0; day <= n; day++) resp[day].clear();
  int day_to_process = 1;
  int pos_to_process = 0;
  for (int day = 1; day <= n; day++) {
    // printf("day = %d\n", day);
    if (day_to_process > day) {
      // printf("day_to_process = %d > %d, continuing\n", day_to_process, day);
      continue;
    }

    for (int j = 0; j < k; j++) {
      if (day_to_process > day) break;
      // printf("using machine %d\n", j);
      while (day_to_process <= day && pos_to_process == requests[day_to_process].size()) {
        day_to_process++;
        pos_to_process = 0;
        if (day_to_process > day) break;
      }
      // printf("day_to_process = %d, pos_to_process = %d\n", day_to_process, pos_to_process);
      if (day_to_process > day) {
        // printf("too late, continuing\n");
        break;
      }
      if (day_to_process + d < day) {
        // printf("too early, returning false\n");
        return false;
      }
      resp[day].push_back(requests[day_to_process][pos_to_process]);
      // printf("added requests[%d][%d] = %d to resp[%d]\n", day_to_process, pos_to_process, requests[day_to_process][pos_to_process], day);
      pos_to_process++;
    }

  }
  return (day_to_process > n);
}

int b_search() {
  int l = 0, r = m;
  while (l < r) {
    int mid = (l + r) / 2;
    if (possible(mid)) r = mid;
    else l = mid + 1;
  }
  return r;
}

int main() {
  cin >> n >> d >> m;
  int x;
  for (int i = 1; i <= m; i++) {
    cin >> x;
    requests[x].push_back(i);
  }
  int ans = b_search();
  cout << ans << endl;
  
  possible(ans);
  for (int i = 1; i <= n; i++) {
    for (int x : resp[i]) cout << x << " ";
    cout << 0 << endl;
  }
  return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool possible(int)':
jobs.cpp:27:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |       while (day_to_process <= day && pos_to_process == requests[day_to_process].size()) {
      |                                       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100