Submission #542210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
542210	2022-03-25T18:08:07 Z	jakubd	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	483 ms	30296 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);

  int n, d, m; cin >> n >> d >> m;
  vector<pair<int, int>> a(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i].first;
    a[i].second = i + 1;
  }

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

  vector<vector<int>> res;

  int lo = 1, hi = m;
  while (lo < hi) {
    int mi = (lo + hi) / 2;

    vector<vector<int>> cur(n + 1);
    queue<int> q; for (int i = 0; i < mi; i++) q.push(0);

    bool ok = true;

    for (int i = 0; i < m; i++) {
      if (q.front() - d <= a[i].first) {
        int nv = max(a[i].first, q.front()); q.pop();
        q.push(nv + 1);
        cur[nv].push_back(a[i].second);
      } else {
        ok = false;
        break;
      }
    }

    if (ok) {
      hi = mi;
      res = cur;
    } else {
      lo = mi + 1;
    }
  }

  cout << lo << "\n";
  for (int i = 1; i <= n; i++) {
    for (int x : res[i]) cout << x << " ";
    cout << "0\n";
  }

  return 0;
};

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	3280 KB	Output is correct
2	Correct	49 ms	3244 KB	Output is correct
3	Correct	42 ms	3268 KB	Output is correct
4	Correct	43 ms	3216 KB	Output is correct
5	Correct	41 ms	3284 KB	Output is correct
6	Correct	43 ms	3288 KB	Output is correct
7	Correct	42 ms	3244 KB	Output is correct
8	Correct	43 ms	3304 KB	Output is correct
9	Correct	62 ms	8064 KB	Output is correct
10	Correct	55 ms	8100 KB	Output is correct
11	Correct	51 ms	3164 KB	Output is correct
12	Correct	104 ms	6120 KB	Output is correct
13	Correct	143 ms	9568 KB	Output is correct
14	Correct	246 ms	13308 KB	Output is correct
15	Correct	245 ms	15108 KB	Output is correct
16	Correct	316 ms	19288 KB	Output is correct
17	Correct	392 ms	23140 KB	Output is correct
18	Correct	450 ms	24344 KB	Output is correct
19	Correct	483 ms	30296 KB	Output is correct
20	Correct	391 ms	23212 KB	Output is correct