제출 #552014

#제출 시각아이디문제언어결과실행 시간메모리
552014acatmeowmeowJob Scheduling (CEOI12_jobs)C++11
90 / 100
406 ms39500 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2") using namespace std; #define int long long signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d, q; cin >> n >> d >> q; vector<vector<int>> day(n + 5), sol; for (int i = 1; i <= q; i++) { int x; cin >> x; day[x].push_back(i); } int l = 1, r = q, ans = q; while (l <= r) { int m = (l + r)/2; vector<vector<int>> res(n + 5); queue<pair<int, int>> pq; bool possible = true; for (int i = 1; i <= n; i++) { int machine = m; for (auto &v : day[i]) pq.push({i, v}); while (machine && pq.size()) { int st = pq.front().first, indx = pq.front().second; pq.pop(); if (i - st > d) possible = false; res[i].push_back(indx); machine--; } } if (possible && pq.empty()) ans = m, r = m - 1, sol = res; else l = m + 1; } cout << ans << '\n'; for (int i = 1; i <= n; i++) { for (auto &v : sol[i]) cout << v << ' '; cout << 0 << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...