답안 #999554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
999554 2024-06-15T19:21:15 Z m_bezrutchka Job Scheduling (CEOI12_jobs) C++17
90 / 100
307 ms 23628 KB
#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

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()) {
      |                                       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 6864 KB Output is correct
2 Correct 32 ms 6856 KB Output is correct
3 Correct 30 ms 7084 KB Output is correct
4 Correct 30 ms 6864 KB Output is correct
5 Correct 30 ms 6868 KB Output is correct
6 Correct 31 ms 6868 KB Output is correct
7 Correct 31 ms 7024 KB Output is correct
8 Correct 30 ms 6860 KB Output is correct
9 Correct 146 ms 7248 KB Output is correct
10 Correct 122 ms 7156 KB Output is correct
11 Correct 28 ms 6996 KB Output is correct
12 Incorrect 46 ms 9140 KB Output isn't correct
13 Correct 66 ms 12372 KB Output is correct
14 Incorrect 118 ms 14932 KB Output isn't correct
15 Correct 110 ms 15956 KB Output is correct
16 Correct 162 ms 19024 KB Output is correct
17 Correct 239 ms 23628 KB Output is correct
18 Correct 187 ms 22096 KB Output is correct
19 Correct 307 ms 23436 KB Output is correct
20 Correct 194 ms 23580 KB Output is correct