Submission #905052

#TimeUsernameProblemLanguageResultExecution timeMemory
905052gun_ganJob Scheduling (CEOI12_jobs)C++17
100 / 100
85 ms920 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX = 1e6 + 5; int N, M, D; int cnt[MX]; bool f(int x) { deque<int> dq; for(int i = 1; i <= N; i++) { if(dq.size() && dq.front() < i) return 0; for(int j = 0; j < cnt[i]; j++) dq.push_back(i + D); for(int j = 0; j < x; j++) { if(dq.empty()) break; dq.pop_front(); } } if(dq.size()) return 0; return 1; } // void p(int x) { // deque<int> dq; // for(int i = 1; i <= N; i++) { // for(int j = 0; j < cnt[i]; j++) dq.push_back(i + D); // for(int j = 0; j < x; j++) { // if(dq.empty()) break; // dq.pop_front(); // } // } // } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> N >> D >> M; for(int i = 0; i < M; i++) { int x; cin >> x; cnt[x]++; } int l = 1, r = M, ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(f(mid)) { r = mid - 1, ans = mid; } else { l = mid + 1; } } cout << ans << '\n'; for(int i = 0; i < N; i++) cout << 0 << '\n'; // p(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...