Submission #642591

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642591	2022-09-20T07:29:45 Z	accidentac	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	375 ms	23232 KB

jobs

#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

#	Verdict	Execution time	Memory	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