Submission #104798

#TimeUsernameProblemLanguageResultExecution timeMemory
104798WLZJob Scheduling (CEOI12_jobs)C++17
40 / 100
203 ms22516 KiB
#include <bits/stdc++.h> using namespace std; int n, d, m; vector<int> a; vector< vector<int> > v; int check(int k) { vector<int> cnt(n + 1, 0); int last = 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[last]; pos = i + d - last; } if ((left + k - 1) / k > pos) { return 0; } last = max(i, last) + (left + k - 1) / k; cnt[last] = 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 (a[i] > 0) { while ((int) ansv[pos].size() < ans && a[i] > 0) { ansv[pos].push_back(v[i].back()); v[i].pop_back(); a[i]--; } 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 (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:56:43: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
       while ((int) ansv[pos].size() < ans && a[i] > 0) {
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...