oj.uz

Submission #1083832

# Submission time Handle Problem Language Result Execution time Memory
1083832 2024-09-04T08:42:37 Z micro7 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 145 ms 13652 KB 
#include <algorithm>
#include <cstdio>
using namespace std;

constexpr int MAXM = 1000000;
int n, m, d;
struct Job {
  int id, date;
} jobs[MAXM];

bool check(int machines) {
  int l = 0, r = 0;
  for (int i = 1; i <= n; ++i) {
    while (r < m && jobs[r].date == i)
      ++r;
    if (l != r && l < m && jobs[l].date + d < i)
      return false;
    l = min(r, l + machines);
  }
  return l == r && r == m;
}
int first_true(int lo, int hi) {
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  return lo;
}

void gen_schedule(int machines) {
  int l = 0, r = 0;
  for (int i = 1; i <= n; ++i) {
    putchar('\n');
    while (r < m && jobs[r].date == i)
      ++r;
    int nl = min(r, l + machines);
    while (l < nl) {
      printf("%d ", jobs[l].id);
      ++l;
    }
    putchar('0');
  }
}

int main() {
  scanf("%d%d%d", &n, &d, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d", &jobs[i].date);
    jobs[i].id = i + 1;
  }
  sort(jobs, jobs + m,
       [](const Job &l, const Job &r) { return l.date < r.date; });

  int mn = first_true(1, m);
  printf("%d", mn);
  gen_schedule(mn);

  return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d%d", &n, &d, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d", &jobs[i].date);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1624 KB Output is correct
2 Correct 12 ms 1628 KB Output is correct
3 Correct 12 ms 1628 KB Output is correct
4 Correct 12 ms 1624 KB Output is correct
5 Correct 13 ms 1716 KB Output is correct
6 Correct 12 ms 1628 KB Output is correct
7 Correct 12 ms 1596 KB Output is correct
8 Correct 12 ms 1716 KB Output is correct
9 Correct 15 ms 1880 KB Output is correct
10 Correct 16 ms 1880 KB Output is correct
11 Correct 16 ms 1628 KB Output is correct
12 Correct 33 ms 3068 KB Output is correct
13 Correct 47 ms 4692 KB Output is correct
14 Correct 72 ms 6100 KB Output is correct
15 Correct 79 ms 7504 KB Output is correct
16 Correct 110 ms 9196 KB Output is correct
17 Correct 135 ms 10580 KB Output is correct
18 Correct 128 ms 12112 KB Output is correct
19 Correct 145 ms 13652 KB Output is correct
20 Correct 124 ms 10580 KB Output is correct