Submission #1085372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085372	2024-09-08T07:00:52 Z	juicy	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	90 ms	16980 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2008 KB	Output is correct
2	Correct	10 ms	2264 KB	Output is correct
3	Correct	10 ms	2012 KB	Output is correct
4	Correct	9 ms	2012 KB	Output is correct
5	Correct	10 ms	1940 KB	Output is correct
6	Correct	14 ms	2164 KB	Output is correct
7	Correct	10 ms	2012 KB	Output is correct
8	Correct	10 ms	2012 KB	Output is correct
9	Correct	15 ms	4444 KB	Output is correct
10	Correct	16 ms	4444 KB	Output is correct
11	Correct	10 ms	1880 KB	Output is correct
12	Correct	20 ms	3420 KB	Output is correct
13	Correct	28 ms	5716 KB	Output is correct
14	Correct	53 ms	7760 KB	Output is correct
15	Correct	47 ms	8784 KB	Output is correct
16	Correct	71 ms	11604 KB	Output is correct
17	Correct	86 ms	13824 KB	Output is correct
18	Correct	86 ms	13728 KB	Output is correct
19	Correct	90 ms	16980 KB	Output is correct
20	Correct	83 ms	13908 KB	Output is correct