Submission #1085362

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1085362	2024-09-08T06:50:58 Z	juicy	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	1000 ms	27744 KB

jobs

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  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> ord(m); iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  vector<vector<int>> events(n);
  auto check = [&](int md) {
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    for (int i = 0, j = 0; i < n; ++i) {
      while (j < m && a[ord[j]] == i) {
        pq.push({i + d, ord[j++]});
      } 
      vector<int>().swap(events[i]);
      int cnt = md;
      while (cnt-- && pq.size()) {
        events[i].push_back(pq.top()[1]);
        pq.pop();
      }
    }
    return !pq.size();
  };
  int l = 0, r = m, res = m;
  while (l <= r) {
    int md = (l + r) / 2;
    if (check(md)) {
      res = md;
      r = md - 1;
    } else {
      l = md + 1;
    }
  }
  check(res);
  cout << res << "\n";
  for (int i = 0; i < n; ++i) {
    for (int j : events[i]) {
      cout << j + 1 << " ";
    }
    cout << 0 << "\n";
  }
  return 0;
}

Subtask #1

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	204 ms	5156 KB	Output isn't correct
2	Incorrect	199 ms	5148 KB	Output isn't correct
3	Incorrect	198 ms	5160 KB	Output isn't correct
4	Incorrect	196 ms	5152 KB	Output isn't correct
5	Incorrect	203 ms	5160 KB	Output isn't correct
6	Incorrect	204 ms	5284 KB	Output isn't correct
7	Incorrect	222 ms	5156 KB	Output isn't correct
8	Incorrect	235 ms	5160 KB	Output isn't correct
9	Incorrect	234 ms	9572 KB	Output isn't correct
10	Incorrect	237 ms	9540 KB	Output isn't correct
11	Correct	142 ms	2672 KB	Output is correct
12	Correct	367 ms	5116 KB	Output is correct
13	Correct	504 ms	7924 KB	Output is correct
14	Correct	696 ms	12244 KB	Output is correct
15	Correct	971 ms	12392 KB	Output is correct
16	Execution timed out	1022 ms	17180 KB	Time limit exceeded
17	Execution timed out	1094 ms	18112 KB	Time limit exceeded
18	Execution timed out	1070 ms	27744 KB	Time limit exceeded
19	Execution timed out	1072 ms	25176 KB	Time limit exceeded
20	Execution timed out	1028 ms	18116 KB	Time limit exceeded