Submission #515133

#TimeUsernameProblemLanguageResultExecution timeMemory
515133mzhJob Scheduling (CEOI12_jobs)C++17
0 / 100
688 ms34872 KiB
#include <bits/stdc++.h> using namespace std; int main() { #ifdef LOCAL freopen("input.in", "r", stdin); #endif ios::sync_with_stdio(false); cin.tie(nullptr); int n, d, m; cin >> n >> d >> m; vector<pair<int, int>> t(m); for (int i = 0; i < m; i++) { cin >> t[i].first; t[i].second = i; } sort(t.begin(), t.end()); vector<int> res; int l = 0, r = m; while (l + 1 < r) { int mid = l + (r - l) / 2; vector<int> cur; multiset<int> st; for (int i = 0; i < mid; i++) { st.insert(0); } bool ok = true; for (int i = 0; i < n; i++) { auto ub = st.upper_bound(t[i].first + d); if (ub == st.end()) { ub--; } if (ub != st.begin()) { ub--; st.erase(ub); st.insert(max(*ub, t[i].first) + 1); } else { ok = false; break; } } (ok ? r : l) = mid; } cout << r << '\n'; for (int i = 0; i < m; i++) { cout << t[i].second + 1 << ' '; if (i == n - 1 || (i && (i + 1) % r == 0)) { cout << "0\n"; } } for (int i = 0; i < n - (m + r - 1) / r; i++) { cout << "0\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...