Submission #1238270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238270		radaiosm7	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	156 ms	13632 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, d, m, day, l, r, ans;
vector<int> requests[100005];
queue<pair<int, int> > q;

bool ok(int x, bool print=false) {
  while (!q.empty()) q.pop();

  for (int i=1; i <= n; ++i) {
    for (int request : requests[i]) q.push(make_pair(i, request));
    int j = 1;

    while (!q.empty() && j <= x) {
      int request = q.front().Y;
      q.pop();
      if (print) printf("%d ", request);
      ++j;
    }

    if (print) printf("0\n");
    if (!q.empty() && q.front().X == i-d) return false;
  }

  return true;
}

int main() {
  scanf("%d%d%d", &n, &d, &m);

  for (int i=1; i <= m; ++i) {
    scanf("%d", &day);
    requests[day].push_back(i);
  }

  l = 1;
  r = m;
  ans = -1;

  while (l <= r) {
    int md = (l+r)/2;

    if (ok(md)) {
      r = md-1;
      ans = md;
    }

    else l = md+1;
  }

  printf("%d\n", ans);
  ok(ans, true);
  return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100