Submission #104814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104814	2019-04-09T10:05:16 Z	WLZ	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	210 ms	20132 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;
    }
    last = max(i, last) + (left + k - 1) / 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:55:43: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       while ((int) ansv[pos].size() < ans && !v[i].empty()) {
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	2516 KB	Output is correct
2	Correct	20 ms	2516 KB	Output is correct
3	Correct	18 ms	2552 KB	Output is correct
4	Correct	20 ms	2544 KB	Output is correct
5	Correct	24 ms	2568 KB	Output is correct
6	Correct	22 ms	2496 KB	Output is correct
7	Correct	19 ms	2552 KB	Output is correct
8	Correct	22 ms	2516 KB	Output is correct
9	Incorrect	52 ms	7288 KB	Output isn't correct
10	Incorrect	53 ms	7268 KB	Output isn't correct
11	Incorrect	29 ms	1996 KB	Output isn't correct
12	Incorrect	37 ms	3704 KB	Output isn't correct
13	Incorrect	91 ms	6520 KB	Output isn't correct
14	Incorrect	160 ms	8784 KB	Output isn't correct
15	Incorrect	138 ms	9132 KB	Output isn't correct
16	Incorrect	188 ms	11188 KB	Output isn't correct
17	Incorrect	210 ms	15556 KB	Output isn't correct
18	Incorrect	201 ms	14748 KB	Output isn't correct
19	Incorrect	206 ms	20132 KB	Output isn't correct
20	Incorrect	204 ms	15592 KB	Output isn't correct