Submission #757816

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757816	2023-06-13T18:56:21 Z	taher	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	357 ms	22104 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	36 ms	3060 KB	Output is correct
2	Correct	32 ms	2984 KB	Output is correct
3	Correct	28 ms	3020 KB	Output is correct
4	Correct	28 ms	3020 KB	Output is correct
5	Correct	29 ms	3056 KB	Output is correct
6	Correct	28 ms	3024 KB	Output is correct
7	Correct	31 ms	3000 KB	Output is correct
8	Correct	32 ms	3004 KB	Output is correct
9	Correct	48 ms	4992 KB	Output is correct
10	Correct	36 ms	4980 KB	Output is correct
11	Correct	36 ms	2540 KB	Output is correct
12	Correct	76 ms	4920 KB	Output is correct
13	Correct	104 ms	7744 KB	Output is correct
14	Correct	175 ms	10888 KB	Output is correct
15	Correct	175 ms	11988 KB	Output is correct
16	Correct	256 ms	15852 KB	Output is correct
17	Correct	294 ms	19528 KB	Output is correct
18	Correct	293 ms	19376 KB	Output is correct
19	Correct	357 ms	22104 KB	Output is correct
20	Correct	279 ms	17908 KB	Output is correct