Submission #570265

#TimeUsernameProblemLanguageResultExecution timeMemory
570265gcconureJob Scheduling (CEOI12_jobs)C++17
15 / 100
372 ms65536 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; ll n,d,m; vector<pair<ll,ll>> v; array<vector<ll>,100001> arr; bool ok(ll dd){ auto copy=v; for(ll i = 0; i < 100001; i++){ arr[i]={}; } ll day = 1; bool works=true; while(!v.empty()){ if(day>n){ works=false; break; } for(ll i = 0; i < dd; i++){ if(v.empty()){ break; } if(v.back().first+d<day){ works=false; break; } arr[day-1].push_back(v.back().second); v.pop_back(); } if(!works){ break; } day++; } v=copy; return works; } int main(){ cin >> n >> d >> m; for(ll i = 0; i < m; i++){ ll x; cin >> x; v.push_back({x,i}); } sort(v.rbegin(), v.rend()); ll l = 1,r=m; array<vector<ll>,100001> cur; while(l<r){ ll mid = (l+r)/2; if(ok(mid)){ cur=arr; r=mid; } else{ l=mid+1; } } cout << l << "\n"; int counter = 0; for(vector<ll> vv:cur){ if(counter==n){ break; } for(ll i:vv){ cout << i+1 << " "; } cout << 0 << "\n"; counter++; } }
#Verdict Execution timeMemoryGrader output
Fetching results...