Submission #989538

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989538	2024-05-28T09:37:48 Z	greenbinjack	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	231 ms	27544 KB

jobs

#include <bits/stdc++.h>
using namespace std;

using LL = long long;

int main() {
  cin.tie(nullptr)->ios_base::sync_with_stdio(false);

  int days, delay, req;
  cin >> days >> delay >> req;
  vector < pair <int, int> > v(req);
  for (int i = 0; i < req; i++) {
    int day;
    cin >> day;
    v[i] = {day, i + 1};
  }

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

  vector < vector <int> > ans;
  int left = 1, right = req;
  while (left < right) {
    int mid = (left + right) >> 1;

    int cur_req = 0;
    vector < vector <int> > adj(days);
    bool ok = false;

    for (int i = 1; i <= days; i++) {
      for (int j = 0; j < mid; j++) {
        if (i < v[cur_req].first) break;

        if (i <= v[cur_req].first + delay) adj[i - 1].push_back(v[cur_req++].second);
        else break;

        if (cur_req == req) ok = true;
      }
    }

    if (ok) {
      right = mid;
      ans = adj;
    } else {
      left = mid + 1;
    }
  }

  cout << right << '\n';
  for (int i = 0; i < days; i++) {
    for (auto c : ans[i]) cout << c << ' ';
    cout << 0 << '\n';
  }

  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2756 KB	Output is correct
2	Correct	19 ms	2760 KB	Output is correct
3	Correct	20 ms	2760 KB	Output is correct
4	Correct	19 ms	2756 KB	Output is correct
5	Correct	19 ms	2808 KB	Output is correct
6	Correct	19 ms	2764 KB	Output is correct
7	Correct	23 ms	2828 KB	Output is correct
8	Correct	19 ms	2764 KB	Output is correct
9	Correct	34 ms	7724 KB	Output is correct
10	Correct	35 ms	7884 KB	Output is correct
11	Correct	24 ms	3152 KB	Output is correct
12	Correct	47 ms	5896 KB	Output is correct
13	Correct	66 ms	8784 KB	Output is correct
14	Correct	117 ms	12156 KB	Output is correct
15	Correct	107 ms	12624 KB	Output is correct
16	Correct	172 ms	16552 KB	Output is correct
17	Correct	189 ms	20412 KB	Output is correct
18	Correct	197 ms	21164 KB	Output is correct
19	Correct	231 ms	27544 KB	Output is correct
20	Correct	199 ms	20444 KB	Output is correct