oj.uz

Submission #1083829

# Submission time Handle Problem Language Result Execution time Memory
1083829 2024-09-04T08:39:58 Z micro7 Job Scheduling (CEOI12_jobs) C++17
40 / 100
 147 ms 17236 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;
    l = min(r, l + machines);
    if (l != r && l < m && jobs[l].date + d < i)
      return false;
  }
  return l == r && r == m;
}
int first_true(int lo, int hi) {
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) {
      // printf("%d true\n", mid);
      hi = mid;
    } else {
      // printf("%d false\n", mid);
      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:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d%d", &n, &d, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d", &jobs[i].date);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1892 KB Output isn't correct
2 Incorrect 13 ms 1952 KB Output isn't correct
3 Incorrect 12 ms 2076 KB Output isn't correct
4 Incorrect 12 ms 2088 KB Output isn't correct
5 Incorrect 13 ms 2008 KB Output isn't correct
6 Incorrect 16 ms 1884 KB Output isn't correct
7 Incorrect 20 ms 1928 KB Output isn't correct
8 Incorrect 13 ms 2020 KB Output isn't correct
9 Incorrect 16 ms 2140 KB Output isn't correct
10 Incorrect 16 ms 2052 KB Output isn't correct
11 Correct 16 ms 1924 KB Output is correct
12 Correct 34 ms 3920 KB Output is correct
13 Correct 49 ms 5712 KB Output is correct
14 Correct 72 ms 8016 KB Output is correct
15 Correct 83 ms 9556 KB Output is correct
16 Correct 111 ms 12056 KB Output is correct
17 Correct 119 ms 13904 KB Output is correct
18 Incorrect 140 ms 15184 KB Output isn't correct
19 Incorrect 147 ms 17236 KB Output isn't correct
20 Correct 128 ms 13908 KB Output is correct