oj.uz

답안 #515778

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
515778 2022-01-19T16:09:08 Z mzh Job Scheduling (CEOI12_jobs) C++17
100 / 100
 511 ms 26976 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
#ifdef LOCAL
  freopen("input.in", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, d, m;
  cin >> n >> d >> m;
  vector<pair<int, int>> t(m);
  for (int i = 0; i < m; i++) {
    cin >> t[i].first;
    t[i].second = i + 1;
  }
  sort(t.begin(), t.end());
  vector<vector<int>> res;
  int l = 0, r = m;
  while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    vector<vector<int>> cur(n + 1);
    queue<int> q;
    for (int i = 0; i < mid; i++) {
      q.push(0);
    }
    bool ok = true;
    for (int i = 0; i < m; i++) {
      if (q.front() - d <= t[i].first) {
        int jt = max(q.front(), t[i].first);
        q.push(jt + 1);
        cur[jt].push_back(t[i].second);
        q.pop();
      } else {
        ok = false;
        break;
      }
    }
    if (ok) {
      r = mid;
      res = cur;
    } else {
      l = mid;
    }
  }
  cout << r << '\n';
  for (int i = 1; i <= n; i++) {
    for (int x : res[i]) {
      cout << x << ' ';
    }
    cout << "0\n";
  }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 2952 KB Output is correct
2 Correct 58 ms 2952 KB Output is correct
3 Correct 52 ms 2960 KB Output is correct
4 Correct 52 ms 2948 KB Output is correct
5 Correct 46 ms 2956 KB Output is correct
6 Correct 47 ms 2964 KB Output is correct
7 Correct 47 ms 2948 KB Output is correct
8 Correct 46 ms 2960 KB Output is correct
9 Correct 59 ms 7764 KB Output is correct
10 Correct 59 ms 7812 KB Output is correct
11 Correct 61 ms 2804 KB Output is correct
12 Correct 105 ms 5340 KB Output is correct
13 Correct 159 ms 8412 KB Output is correct
14 Correct 242 ms 11396 KB Output is correct
15 Correct 251 ms 13204 KB Output is correct
16 Correct 322 ms 16552 KB Output is correct
17 Correct 420 ms 19800 KB Output is correct
18 Correct 454 ms 21180 KB Output is correct
19 Correct 511 ms 26976 KB Output is correct
20 Correct 401 ms 19976 KB Output is correct