Submission #999554

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999554	2024-06-15T19:21:15 Z	m_bezrutchka	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	307 ms	23628 KB

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

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

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