Submission #858033

#TimeUsernameProblemLanguageResultExecution timeMemory
858033AminMDNZJob Scheduling (CEOI12_jobs)C++14
55 / 100
359 ms20280 KiB
#include<bits/stdc++.h> using namespace std; vector<pair<int, int>> arr; int n, m, d; vector<vector<int>> day; bool f(int mm){ int del = 0; day.clear(); day.resize(n+1); queue<int> mac; for(int i=0;i<mm;i++) mac.push(1); for(int i=0;i<m;i++){ int r = mac.front(); del = max(r - arr[i].first, del); if(del > d) return false; day[r].push_back(arr[i].second); mac.pop(); mac.push(r+1); } return true; } int main(){ cin>>n>>d>>m; arr.resize(m); for(int i=0;i<m;i++){ arr[i].second = i; cin>>arr[i].first; } sort(arr.begin(), arr.end()); int mm; int r = m; int l = 1; int ans = -1; while(r >= l){ mm = l + (r - l)/2; if(f(mm)){ r = mm - 1; ans = mm; } else{ l = mm + 1; } } f(ans); cout<<ans<<endl; for(int i=1;i<n+1;i++){ for(auto t : day[i]) cout<<t+1<<" "; cout<<"0\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...