Submission #1208922

#TimeUsernameProblemLanguageResultExecution timeMemory
1208922Vivek_03_Job Scheduling (CEOI12_jobs)C++20
100 / 100
308 ms26908 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; bool f(int machines, vector<vector<int>>& result, vector<pair<int,int>>& v, int delay, int n) { int ptr = 1; for(int i=1;i<=n;i++) { for(int j=0;j<machines;j++) { if(v[ptr].first > i) // we need to go to ahead day because now tasks are assigned at days v[ptr].first or later break; if(v[ptr].first + delay >= i) { result[i].push_back(v[ptr].second); ptr++; } else return false; if(ptr==v.size()) return true; } } return true; } int main() { int n,d,m; cin>>n>>d>>m; vector<pair<int,int>> v(m+1); for(int i=1;i<=m;i++) { int start; cin>>start; v[i] = {start,i}; } sort(v.begin(),v.end()); vector<vector<int>> result(n+1); int l=1,r=m; while(l<=r) { int mid = l + (r-l)/2; vector<vector<int>> temp(n+1); if(f(mid,temp,v,d,n)) { r=mid-1; result = temp; } else l=mid+1; } cout<<l<<'\n'; for(int i=1;i<=n;i++) { for(int j=0;j<result[i].size();j++) { cout<<result[i][j]<<" "; } cout<<"0\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...