Submission #499651

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
499651	2021-12-29T06:58:04 Z	Shreyan_Paliwal	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	547 ms	13736 KB

jobs

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>> jobs;
int                    n, d, m;

bool works(int mid) {
  int counter = mid;
  for (int i = 0; i < m; i++) {
    if ((counter / mid) <= jobs[i].first + d) {
      if ((counter / mid) < jobs[i].first) {
        counter = jobs[i].first * mid + 1;
      } else {
        counter++;
      }
    } else {
      return false;
    }
  }
  counter--;
  return (counter / mid) <= n;
}

int main() {
  cin >> n >> d >> m;

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

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

  int lo = 1;
  int hi = 1000000;
  while (lo != hi) {
    int mid = (lo + hi) / 2;
    if (works(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }

  cout << lo << endl;

  int counter = 0;
  for (int i = 1; i < n + 1; i++) {
    if (counter == m) {
      cout << 0 << endl;
      continue;
    }
    if (jobs[counter].first <= i) {
      for (int j = 0; j < lo; j++) {
        if (counter == m) break;
        cout << jobs[counter++].second << " ";
      }
    }
    cout << 0 << endl;
  }

  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	1580 KB	Output is correct
2	Correct	56 ms	1764 KB	Output is correct
3	Correct	50 ms	1604 KB	Output is correct
4	Correct	50 ms	1596 KB	Output is correct
5	Correct	50 ms	1680 KB	Output is correct
6	Correct	49 ms	1604 KB	Output is correct
7	Correct	50 ms	1588 KB	Output is correct
8	Correct	61 ms	1708 KB	Output is correct
9	Correct	159 ms	1840 KB	Output is correct
10	Correct	156 ms	1860 KB	Output is correct
11	Correct	48 ms	1604 KB	Output is correct
12	Correct	107 ms	3132 KB	Output is correct
13	Correct	146 ms	4548 KB	Output is correct
14	Correct	228 ms	6104 KB	Output is correct
15	Correct	252 ms	7532 KB	Output is correct
16	Correct	317 ms	9024 KB	Output is correct
17	Correct	406 ms	10564 KB	Output is correct
18	Correct	402 ms	12052 KB	Output is correct
19	Correct	547 ms	13736 KB	Output is correct
20	Correct	382 ms	10496 KB	Output is correct