제출 #1275295

#제출 시각아이디문제언어결과실행 시간메모리
1275295m_a_dJob Scheduling (CEOI12_jobs)C++20
100 / 100
282 ms20896 KiB
#include <bits/stdc++.h> using namespace std; #define int long long bool check(vector<pair<int, int>>& jobs, int machine_a, int d, int n) { int jobs_ptr=0; for(int i=0; i<n; ++i) { if(jobs_ptr==jobs.size()) return 1; if(i>jobs[jobs_ptr].first+d) return 0; int available=machine_a; while(available>0 && jobs_ptr<jobs.size() && jobs[jobs_ptr].first<=i) { available--; jobs_ptr++; } if(jobs_ptr==jobs.size()) return 1; if(i>jobs[jobs_ptr].first+d) return 0; } cout << jobs_ptr; return 0; } int32_t main() { int n, d, m; cin >> n >> d >> m; vector<pair<int, int>> jobs(m); for(int i=0; i<m; ++i) cin >> jobs[i].first, jobs[i].first--, jobs[i].second=i; sort(jobs.begin(), jobs.end()); int lo=1, hi=m; int mid; while(lo<hi) { mid=lo+(hi-lo)/2; if(check(jobs, mid, d, n)) { hi=mid; } else { lo=mid+1; } } cout << hi << "\n"; int jobs_ptr=0; for(int i=0; i<n; ++i) { int available=hi; while(available>0 && jobs_ptr<jobs.size() && jobs[jobs_ptr].first<=i) { available--; cout << jobs[jobs_ptr].second+1 << " "; jobs_ptr++; } cout << 0 << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...