oj.uz

답안 #1085365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1085365 2024-09-08T06:53:13 Z juicy Job Scheduling (CEOI12_jobs) C++17
90 / 100
 1000 ms 16548 KB 
#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

# 결과 실행 시간 메모리 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