Submission #104821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104821	2019-04-09T10:12:19 Z	WLZ	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	239 ms	20216 KB

jobs

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

int n, d, m;
vector<int> a;
vector< vector<int> > v;

int check(int k) {
  int last = 0, cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0) {
      continue;
    }
    int left = a[i];
    int pos = d + 1;
    if (last >= i) {
      left -= k - cnt;
      pos = i + d - last;
    }
    if ((left + k - 1) / k > pos) {
      return 0;
    }
    if (last >= i) {
      last += 1 + left / k;
    } else {
      last = i + left / k;
    }
    cnt = left % k;
  }
  return 1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> d >> m;
  a.assign(n + 1, 0);
  v.resize(n + 1);
  for (int i = 1; i <= m; i++) {
    int x;
    cin >> x;
    a[x]++;
    v[x].push_back(i);
  }
  int lo = 1, hi = m, ans;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (check(mid)) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  vector< vector<int> > ansv(n + 1);
  for (int i = 1; i <= n; i++) {
    int pos = i;
    while (pos <= n && !v[i].empty()) {
      while ((int) ansv[pos].size() < ans && !v[i].empty()) {
        ansv[pos].push_back(v[i].back());
        v[i].pop_back();
      }
      pos++;
    }
  }
  cout << ans << '\n';
  for (int i = 1; i <= n; i++) {
    for (auto& x : ansv[i]) {
      cout << x << ' ';
    }
    cout << 0 << '\n';
  }
  return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:59:43: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       while ((int) ansv[pos].size() < ans && !v[i].empty()) {
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2544 KB	Output is correct
2	Correct	20 ms	2552 KB	Output is correct
3	Correct	23 ms	2552 KB	Output is correct
4	Correct	18 ms	2552 KB	Output is correct
5	Correct	18 ms	2540 KB	Output is correct
6	Correct	25 ms	2672 KB	Output is correct
7	Correct	20 ms	2672 KB	Output is correct
8	Correct	21 ms	2552 KB	Output is correct
9	Correct	32 ms	7296 KB	Output is correct
10	Correct	38 ms	7288 KB	Output is correct
11	Correct	25 ms	2040 KB	Output is correct
12	Correct	69 ms	3704 KB	Output is correct
13	Correct	58 ms	6520 KB	Output is correct
14	Correct	189 ms	8840 KB	Output is correct
15	Correct	132 ms	8460 KB	Output is correct
16	Correct	184 ms	11196 KB	Output is correct
17	Correct	239 ms	15740 KB	Output is correct
18	Correct	159 ms	14712 KB	Output is correct
19	Correct	222 ms	20216 KB	Output is correct
20	Correct	235 ms	15840 KB	Output is correct