Submission #1249200

#TimeUsernameProblemLanguageResultExecution timeMemory
1249200joao_pauloJob Scheduling (CEOI12_jobs)C++20
91 / 100
328 ms22044 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; int n, d, w; vector<pii> v; vector<vector<int>> dia; bool f(int m){ queue<int> q; for(int i = 0; i < n; i++){ dia[i].clear(); } for(int i = 0; i < m; i++){ q.push(0); } for(int i = 0; i < w; i++){ if(q.empty())return false; if(q.front() > v[i].first){ if(q.front()-v[i].first > d)return false; dia[q.front()].push_back(v[i].second); if(q.front()+1 > n){ q.pop(); continue; } q.push(q.front()+1); q.pop(); } else{ dia[v[i].first].push_back(v[i].second); q.pop(); q.push(v[i].first+1); } } return true; } void buscab(){ int ini = 1, fim = w, resp = 1; while(ini <= fim){ int m = (ini+fim)/2; if(f(m)){ fim = m-1; resp = m; } else{ ini = m+1; } } f(resp); cout << resp << '\n'; for(int i = 1; i < n+1; i++){ for(auto& x : dia[i])cout << x << " "; cout << "0\n"; } } int main(){ cin >> n >> d >> w; v.reserve(w); dia.reserve(n+1); for(int i = 0; i < w; i++){ int x; cin >> x; v.push_back(make_pair(x, i+1)); } for(int i = 0; i < n+1; i++)dia.push_back({}); sort(v.begin(), v.end()); buscab(); }
#Verdict Execution timeMemoryGrader output
Fetching results...