Submission #1083829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083829		micro7	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	147 ms	17236 KiB

jobs

#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 (stderr)

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 / 100