Submission #1248763

#TimeUsernameProblemLanguageResultExecution timeMemory
1248763vpinxJob Scheduling (CEOI12_jobs)C++20
100 / 100
191 ms31172 KiB
#include <bits/stdc++.h> using namespace std; #define int long long void solve() { int n, d, m; cin >> n >> d >> m; vector<pair<int, int>> v(m); for (int i = 0; i < m; i++) { cin >> v[i].first; v[i].second = i; } sort(v.begin(), v.end()); int ans, l = 1, r = m; while (l <= r) { int mid = (l + r) / 2, idx = 0; bool good = false, bad = false; for (int i = 0; i < n; i++) { for (int j = 0; j < mid; j++) { auto cur = v[idx]; if (cur.first + d < i + 1) { bad = true; break; } if (cur.first <= i + 1) idx++; else break; if (idx == m) { good = true; break; } } if (good or bad) break; } if (good) { r = mid - 1; ans = mid; }else l = mid + 1; } vector<vector<int>> schedule(n); int idx = 0; bool good = false; for (int i = 0; i < n; i++) { for (int j = 0; j < ans; j++) { auto cur = v[idx]; if (cur.first <= i + 1) { schedule[i].push_back(cur.second); idx++; }else break; if (idx == m) { good = true; break; } } if (good) break; } cout << ans << "\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < schedule[i].size(); j++) cout << schedule[i][j] + 1 << " "; cout << 0 << "\n"; } } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...