oj.uz

답안 #642591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642591 2022-09-20T07:29:45 Z accidentac Job Scheduling (CEOI12_jobs) C++17
100 / 100
 375 ms 23232 KB 
#include <bits/stdc++.h>
using namespace std;

int n, d, m;
vector<array<int, 2>> jobs;

// return true if can use count no. of machines to handle all jobs
bool ok(int count) {
  queue<int> q;
  for (int i = 1, j = 0; i <= n; i++) {
    while (j < m && jobs[j][0] == i) {
      q.push(j++);
    }
    if (q.size() && i - jobs[q.front()][0] > d) return false;
    for (int rep = 0; rep < count && !q.empty(); rep++) {
      q.pop();
    }
  }
  return true;
}

vector<vector<int>> form(int count) {
  vector<vector<int>> ans(n);

  queue<int> q;
  for (int i = 1, j = 0; i <= n; i++) {
    vector<int> cur;
    while (j < m && jobs[j][0] == i) {
      q.push(j++);
    }
    for (int rep = 0; rep < count && !q.empty(); rep++) {
      ans[i - 1].push_back(jobs[q.front()][1]);
      q.pop();
    }
    ans[i - 1].push_back(0);
  }

  return ans;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> d >> m;
  jobs = vector<array<int, 2>>(m);
  for (int i = 0; i < m; i++) {
    cin >> jobs[i][0];
    jobs[i][1] = i + 1;
  }
  sort(jobs.begin(), jobs.end());
  int lo = 1, hi = m, ans = m;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (ok(mid)) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  cout << ans << '\n';
  for (auto row : form(ans)) {
    for (int x : row) {
      cout << x;
      if (x != 0) cout << ' ';
    }
    cout << '\n';
  }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2912 KB Output is correct
2 Correct 29 ms 2932 KB Output is correct
3 Correct 32 ms 2920 KB Output is correct
4 Correct 30 ms 2848 KB Output is correct
5 Correct 29 ms 2940 KB Output is correct
6 Correct 38 ms 2900 KB Output is correct
7 Correct 29 ms 2904 KB Output is correct
8 Correct 29 ms 2956 KB Output is correct
9 Correct 53 ms 7764 KB Output is correct
10 Correct 48 ms 7756 KB Output is correct
11 Correct 43 ms 2248 KB Output is correct
12 Correct 70 ms 4292 KB Output is correct
13 Correct 102 ms 6640 KB Output is correct
14 Correct 143 ms 9136 KB Output is correct
15 Correct 178 ms 9652 KB Output is correct
16 Correct 209 ms 12020 KB Output is correct
17 Correct 265 ms 15944 KB Output is correct
18 Correct 336 ms 16740 KB Output is correct
19 Correct 375 ms 23232 KB Output is correct
20 Correct 259 ms 15908 KB Output is correct