oj.uz

답안 #542210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
542210 2022-03-25T18:08:07 Z jakubd Job Scheduling (CEOI12_jobs) C++17
100 / 100
 483 ms 30296 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);

  int n, d, m; cin >> n >> d >> m;
  vector<pair<int, int>> a(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i].first;
    a[i].second = i + 1;
  }

  sort(a.begin(), a.end());

  vector<vector<int>> res;

  int lo = 1, hi = m;
  while (lo < hi) {
    int mi = (lo + hi) / 2;

    vector<vector<int>> cur(n + 1);
    queue<int> q; for (int i = 0; i < mi; i++) q.push(0);

    bool ok = true;

    for (int i = 0; i < m; i++) {
      if (q.front() - d <= a[i].first) {
        int nv = max(a[i].first, q.front()); q.pop();
        q.push(nv + 1);
        cur[nv].push_back(a[i].second);
      } else {
        ok = false;
        break;
      }
    }

    if (ok) {
      hi = mi;
      res = cur;
    } else {
      lo = mi + 1;
    }
  }

  cout << lo << "\n";
  for (int i = 1; i <= n; i++) {
    for (int x : res[i]) cout << x << " ";
    cout << "0\n";
  }

  return 0;
};

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 3280 KB Output is correct
2 Correct 49 ms 3244 KB Output is correct
3 Correct 42 ms 3268 KB Output is correct
4 Correct 43 ms 3216 KB Output is correct
5 Correct 41 ms 3284 KB Output is correct
6 Correct 43 ms 3288 KB Output is correct
7 Correct 42 ms 3244 KB Output is correct
8 Correct 43 ms 3304 KB Output is correct
9 Correct 62 ms 8064 KB Output is correct
10 Correct 55 ms 8100 KB Output is correct
11 Correct 51 ms 3164 KB Output is correct
12 Correct 104 ms 6120 KB Output is correct
13 Correct 143 ms 9568 KB Output is correct
14 Correct 246 ms 13308 KB Output is correct
15 Correct 245 ms 15108 KB Output is correct
16 Correct 316 ms 19288 KB Output is correct
17 Correct 392 ms 23140 KB Output is correct
18 Correct 450 ms 24344 KB Output is correct
19 Correct 483 ms 30296 KB Output is correct
20 Correct 391 ms 23212 KB Output is correct