Submission #637895

#	Time	Username	Problem	Language	Result	Execution time	Memory
637895		SeyedAmirHs	Job Scheduling (CEOI12_jobs)	C++17	30 / 100	183 ms	18524 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, d, m;
  cin >> n >> d >> m;
  vector<vector<int>> works_in_day(n);
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    x--;
    works_in_day[x].push_back(i);
  }

  auto can = [&](int y) -> bool {
    int day = 0;
    queue<int> q;
    while (day < n) {
      for (auto &x : works_in_day[day]) {
        q.push(day + d);
      }
      int cnt = 0;
      while (cnt < y and !q.empty()) {
        if (day >= q.front()) {
          return false;
        }
        q.pop();
        cnt++;
      }
      day++;
    }
    return q.empty();
  };

  int l = 0, r = n;
  while (r - l > 1) {
    int mid = l + (r - l) / 2;
    if (can(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  int need = r;
  queue<int> q;
  cout << need << '\n';
  for (int i = 0; i < n; i++) {
    for (auto &x : works_in_day[i]) {
      q.push(x);
    }
    int cnt = 0;
    while (cnt < need and !q.empty()) {
      cout << q.front() + 1 << ' ';
      q.pop();
      cnt++;
    }
    cout << 0 << '\n';
  }
}

Compilation message (stderr)

jobs.cpp: In lambda function:
jobs.cpp:25:18: warning: unused variable 'x' [-Wunused-variable]
   25 |       for (auto &x : works_in_day[day]) {
      |                  ^

• Subtask 1: 30 / 100