Submission #1085368

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085368	2024-09-08T06:54:59 Z	juicy	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	18256 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<int> a(m);
  for (int i = 0; i < m; ++i) {
    cin >> a[i]; -- a[i];
  }
  vector<int> ord(m); iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  vector<vector<int>> events(n);
  auto check = [&](int md) -> bool {
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    for (int i = 0, j = 0; i < n; ++i) {
      if (pq.size() && pq.top()[0] < i) {
        return 0;
      }
      while (j < m && a[ord[j]] == i) {
        pq.push({i + d, ord[j++]});
      } 
      int cnt = md;
      while (cnt-- && pq.size()) {
        pq.pop();
      }
    }
    return !pq.size();
  };
  auto qry = [&](int md) {
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    for (int i = 0, j = 0; i < n; ++i) {
      while (j < m && a[ord[j]] == i) {
        pq.push({i + d, ord[j++]});
      } 
      int cnt = md;
      while (cnt-- && pq.size()) {
        events[i].push_back(pq.top()[1]);
        pq.pop();
      }
    }
  };
  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);
  cout << res << "\n";
  for (int i = 0; i < n; ++i) {
    for (int j : events[i]) {
      cout << j + 1 << " ";
    }
    cout << 0 << "\n";
  }
  return 0;
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	186 ms	4032 KB	Output is correct
2	Correct	196 ms	3968 KB	Output is correct
3	Correct	189 ms	4032 KB	Output is correct
4	Correct	192 ms	3992 KB	Output is correct
5	Correct	186 ms	4036 KB	Output is correct
6	Correct	186 ms	4000 KB	Output is correct
7	Correct	185 ms	3968 KB	Output is correct
8	Correct	198 ms	4100 KB	Output is correct
9	Correct	199 ms	5040 KB	Output is correct
10	Correct	172 ms	5200 KB	Output is correct
11	Correct	120 ms	2644 KB	Output is correct
12	Correct	334 ms	4900 KB	Output is correct
13	Correct	469 ms	7508 KB	Output is correct
14	Correct	582 ms	10600 KB	Output is correct
15	Correct	757 ms	11092 KB	Output is correct
16	Correct	670 ms	13896 KB	Output is correct
17	Correct	866 ms	18256 KB	Output is correct
18	Execution timed out	1033 ms	8784 KB	Time limit exceeded
19	Execution timed out	1047 ms	11904 KB	Time limit exceeded
20	Correct	899 ms	18064 KB	Output is correct