oj.uz

답안 #757816

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757816 2023-06-13T18:56:21 Z taher Job Scheduling (CEOI12_jobs) C++17
100 / 100
 357 ms 22104 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  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> order(m);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
 
  vector<vector<int>> days(n);
 
  auto Can = [&](int machines) {
    for (int i = 0; i < n; i++) {
      days[i].clear();
    }
    int day = 0;
    int emptyMachines = machines;
    for (int id = 0; id < m; id++) {
      int cur = a[order[id]];
      if (cur > day) {
        day = cur;
        emptyMachines = machines;
      } else if (cur + d < day) {
        return false;
      }
      days[day].push_back(order[id]);
      if (--emptyMachines == 0) {
        day++;
        emptyMachines = machines;
      }
    }
    return true;
  };
 
  int low = 1, high = 1000000000;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (Can(mid)) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
 
  Can(high + 1);
 
  cout << high + 1 << '\n';
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < (int) days[i].size(); j++) {
      if (j > 0) {
        cout << " ";
      }
      cout << 1 + days[i][j];
    }
    if ((int) days[i].size() > 0) {
      cout << " ";
    }
    cout << "0\n";
  }
  return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 3060 KB Output is correct
2 Correct 32 ms 2984 KB Output is correct
3 Correct 28 ms 3020 KB Output is correct
4 Correct 28 ms 3020 KB Output is correct
5 Correct 29 ms 3056 KB Output is correct
6 Correct 28 ms 3024 KB Output is correct
7 Correct 31 ms 3000 KB Output is correct
8 Correct 32 ms 3004 KB Output is correct
9 Correct 48 ms 4992 KB Output is correct
10 Correct 36 ms 4980 KB Output is correct
11 Correct 36 ms 2540 KB Output is correct
12 Correct 76 ms 4920 KB Output is correct
13 Correct 104 ms 7744 KB Output is correct
14 Correct 175 ms 10888 KB Output is correct
15 Correct 175 ms 11988 KB Output is correct
16 Correct 256 ms 15852 KB Output is correct
17 Correct 294 ms 19528 KB Output is correct
18 Correct 293 ms 19376 KB Output is correct
19 Correct 357 ms 22104 KB Output is correct
20 Correct 279 ms 17908 KB Output is correct