Submission #532341

#TimeUsernameProblemLanguageResultExecution timeMemory
532341Alex_tz307Job Scheduling (CEOI12_jobs)C++17
0 / 100
863 ms23252 KiB
#include <bits/stdc++.h> using namespace std; const int kN = 1e5; const int kM = 1e6; int n, d, m; pair<int, int> a[kM]; vector<int> sol[1 + kN]; /* 8 2 12 1 2 4 2 1 3 5 6 2 3 6 4 */ bool check(int k, bool ok = false) { priority_queue<int, vector<int>, greater<int>> pq; for (int i = 0; i < k; ++i) { pq.emplace(0); } for (int i = 0; i < m; ++i) { int t = pq.top(); pq.pop(); if (t > a[i].first + d) { return false; } if (t < a[i].first) { t = a[i].first; } pq.emplace(t + 1); if (ok) { sol[t].emplace_back(a[i].second + 1); } } return true; } void testCase() { cin >> n >> d >> m; for (int i = 0; i < m; ++i) { cin >> a[i].first; a[i].second = i; } sort(a, a + m); int l = 1, r = m, ans = m; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } cout << ans << '\n'; check(ans, true); for (int i = 1; i <= n; ++i) { sol[i].emplace_back(0); for (int x : sol[i]) { cout << x << ' '; } cout << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tests = 1; for (int tc = 0; tc < tests; ++tc) { testCase(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...