Submission #711422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
711422	2023-03-16T22:54:19 Z	narvalo	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	333 ms	20428 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, d, m;
  cin >> n >> d >> m;
  vector<int> a(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i];
    --a[i];
  }
  vector<int> order(m);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return a[i] < a[j];
  });

  vector<vector<int>> days(n);

  auto Can = [&](int machines) {
    for (int i = 0; i < n; i++) {
      days[i].clear();
    }
    int day = 0;
    int emptyMachines = machines;
    for (int id = 0; id < m; id++) {
      int cur = a[order[id]];
      if (cur > day) {
        day = cur;
        emptyMachines = machines;
      } else if (cur + d < day) {
        return false;
      }
      days[day].push_back(order[id]);
      if (--emptyMachines == 0) {
        day++;
        emptyMachines = machines;
      }
    }
    return true;
  };

  int low = 1, high = 1000000000;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (Can(mid)) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  Can(high + 1);

  cout << high + 1 << '\n';
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < (int) days[i].size(); j++) {
      if (j > 0) {
        cout << " ";
      }
      cout << 1 + days[i][j];
    }
    if ((int) days[i].size() > 0) {
      cout << " ";
    }
    cout << "0\n";
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	3020 KB	Output is correct
2	Correct	29 ms	2972 KB	Output is correct
3	Correct	30 ms	3012 KB	Output is correct
4	Correct	28 ms	2956 KB	Output is correct
5	Correct	29 ms	2972 KB	Output is correct
6	Correct	28 ms	3028 KB	Output is correct
7	Correct	29 ms	2960 KB	Output is correct
8	Correct	28 ms	2948 KB	Output is correct
9	Correct	35 ms	5016 KB	Output is correct
10	Correct	37 ms	4980 KB	Output is correct
11	Correct	34 ms	2412 KB	Output is correct
12	Correct	67 ms	4484 KB	Output is correct
13	Correct	108 ms	6884 KB	Output is correct
14	Correct	154 ms	9284 KB	Output is correct
15	Correct	170 ms	10572 KB	Output is correct
16	Correct	227 ms	13396 KB	Output is correct
17	Correct	265 ms	16640 KB	Output is correct
18	Correct	265 ms	16684 KB	Output is correct
19	Correct	333 ms	20428 KB	Output is correct
20	Correct	264 ms	16648 KB	Output is correct