Submission #1085372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085372		juicy	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	90 ms	16980 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n, d, m; cin >> n >> d >> m;
  vector<vector<int>> buc(n);
  for (int i = 0; i < m; ++i) {
    int x; cin >> x; --x;
    buc[x].push_back(i);
  }
  auto check = [&](int md) -> bool {
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    for (int i = 0; i < n; ++i) {
      if (pq.size() && pq.top()[0] < i) {
        return 0;
      }
      if (buc[i].size()) {
        pq.push({i + d, buc[i].size()});
      }
      int cnt = md;
      while (cnt && pq.size()) {
        auto [u, v] = pq.top();
        pq.pop();
        int k = min(cnt, v);
        v -= k;
        cnt -= k;
        if (v) {
          pq.push({u, v});
        }
      }
    }
    return !pq.size();
  };
  auto qry = [&](int md) {
    cout << md << "\n";
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    for (int i = 0; i < n; ++i) {
      if (buc[i].size()) {
        pq.push({i + d, buc[i].size()});
      }
      int cnt = md;
      while (cnt && pq.size()) {
        auto [u, v] = pq.top();
        pq.pop();
        int k = min(cnt, v);
        v -= k;
        cnt -= k;
        while (k--) {
          cout << buc[u - d].back() + 1 << " ";
          buc[u - d].pop_back();
        }
        if (v) {
          pq.push({u, v});
        }
      }
      cout << 0 << "\n";
    }
  };
  int l = 0, r = m, res = m;
  while (l <= r) {
    int md = (l + r) / 2;
    if (check(md)) {
      res = md;
      r = md - 1;
    } else {
      l = md + 1;
    }
  }
  qry(res);
  return 0;
}

Compilation message (stderr)

jobs.cpp: In lambda function:
jobs.cpp:27:36: warning: narrowing conversion of '(&(& buc)->std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   27 |         pq.push({i + d, buc[i].size()});
      |                         ~~~~~~~~~~~^~
jobs.cpp: In lambda function:
jobs.cpp:48:36: warning: narrowing conversion of '(&(& buc)->std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   48 |         pq.push({i + d, buc[i].size()});
      |                         ~~~~~~~~~~~^~

• Subtask 1: 100 / 100