제출 #674293

#제출 시각아이디문제언어결과실행 시간메모리
674293thienbao1602Job Scheduling (CEOI12_jobs)C++17
60 / 100
346 ms26472 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define vi vector<int> using namespace std; int N, D, M; vector<pair<int, int>> jobs; pair<bool, vector<vi>> check(const vector<pair<int, int>> &jobs, int machine) { vector<vi> schedule(N); int id_job = 0; for(int i=1; i<=N; i++) { for(int cur_machine=0; cur_machine<machine; cur_machine++) { if (jobs[id_job].fi > i) break; if (jobs[id_job].fi + D >= i) { schedule[i - 1].pb(jobs[id_job++].se); } else return make_pair(false, schedule); if (id_job == M) return make_pair(true, schedule); } } return make_pair(false, schedule); } void solve() { cin >> N >> D >> M; vector<pair<int, int>> jobs(M); for(int i=0; i<M; i++) { int x; cin >> x; jobs[i] = make_pair(x, i + 1); } sort(jobs.begin(), jobs.end()); vector<vi> ans; int l = 1, r = N; while(l < r) { int m = (l + r) >> 1; pair<bool, vector<vi>> curResult = check(jobs, m); if (curResult.fi) { r = m; ans = curResult.se; } else { l = m + 1; } } cout << l << "\n"; for(int i=0; i<N; i++) { for(int &idx : ans[i]) { cout << idx << " "; } cout << 0 << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...