Submission #515778

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515778	2022-01-19T16:09:08 Z	mzh	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	511 ms	26976 KB

jobs

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

int main() {
#ifdef LOCAL
  freopen("input.in", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, d, m;
  cin >> n >> d >> m;
  vector<pair<int, int>> t(m);
  for (int i = 0; i < m; i++) {
    cin >> t[i].first;
    t[i].second = i + 1;
  }
  sort(t.begin(), t.end());
  vector<vector<int>> res;
  int l = 0, r = m;
  while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    vector<vector<int>> cur(n + 1);
    queue<int> q;
    for (int i = 0; i < mid; i++) {
      q.push(0);
    }
    bool ok = true;
    for (int i = 0; i < m; i++) {
      if (q.front() - d <= t[i].first) {
        int jt = max(q.front(), t[i].first);
        q.push(jt + 1);
        cur[jt].push_back(t[i].second);
        q.pop();
      } else {
        ok = false;
        break;
      }
    }
    if (ok) {
      r = mid;
      res = cur;
    } else {
      l = mid;
    }
  }
  cout << r << '\n';
  for (int i = 1; i <= n; i++) {
    for (int x : res[i]) {
      cout << x << ' ';
    }
    cout << "0\n";
  }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	2952 KB	Output is correct
2	Correct	58 ms	2952 KB	Output is correct
3	Correct	52 ms	2960 KB	Output is correct
4	Correct	52 ms	2948 KB	Output is correct
5	Correct	46 ms	2956 KB	Output is correct
6	Correct	47 ms	2964 KB	Output is correct
7	Correct	47 ms	2948 KB	Output is correct
8	Correct	46 ms	2960 KB	Output is correct
9	Correct	59 ms	7764 KB	Output is correct
10	Correct	59 ms	7812 KB	Output is correct
11	Correct	61 ms	2804 KB	Output is correct
12	Correct	105 ms	5340 KB	Output is correct
13	Correct	159 ms	8412 KB	Output is correct
14	Correct	242 ms	11396 KB	Output is correct
15	Correct	251 ms	13204 KB	Output is correct
16	Correct	322 ms	16552 KB	Output is correct
17	Correct	420 ms	19800 KB	Output is correct
18	Correct	454 ms	21180 KB	Output is correct
19	Correct	511 ms	26976 KB	Output is correct
20	Correct	401 ms	19976 KB	Output is correct