Submission #1085365

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085365	2024-09-08T06:53:13 Z	juicy	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	1000 ms	16548 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++]});
      } 
      vector<int>().swap(events[i]);
      int cnt = md;
      while (cnt-- && pq.size()) {
        events[i].push_back(pq.top()[1]);
        pq.pop();
      }
    }
    return !pq.size();
  };
  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;
    }
  }
  check(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	183 ms	4316 KB	Output is correct
2	Correct	192 ms	4316 KB	Output is correct
3	Correct	203 ms	4444 KB	Output is correct
4	Correct	190 ms	4316 KB	Output is correct
5	Correct	183 ms	4316 KB	Output is correct
6	Correct	190 ms	4316 KB	Output is correct
7	Correct	181 ms	4436 KB	Output is correct
8	Correct	181 ms	4320 KB	Output is correct
9	Correct	184 ms	5228 KB	Output is correct
10	Correct	176 ms	5160 KB	Output is correct
11	Correct	126 ms	2384 KB	Output is correct
12	Correct	345 ms	4308 KB	Output is correct
13	Correct	483 ms	6740 KB	Output is correct
14	Correct	623 ms	9380 KB	Output is correct
15	Correct	775 ms	10452 KB	Output is correct
16	Correct	715 ms	12828 KB	Output is correct
17	Correct	976 ms	16548 KB	Output is correct
18	Execution timed out	1076 ms	11068 KB	Time limit exceeded
19	Execution timed out	1078 ms	13924 KB	Time limit exceeded
20	Correct	938 ms	16352 KB	Output is correct