Submission #1003397

#TimeUsernameProblemLanguageResultExecution timeMemory
1003397AtinaRJob Scheduling (CEOI12_jobs)C++14
100 / 100
278 ms22280 KiB
#include <bits/stdc++.h> using namespace std; const int MAX=1e6+10; const int N=1e5+10; pair<int,int> niza[MAX]; int n,d,m; vector<int> ress[N]; bool work(int mid) { if(mid<=0)return false; if(mid>=m)return true; int i=0; for(int day=1; day<=n; day++) { ress[day].clear(); for(int j=0; j<mid; j++) { if(i>=m)break; if(niza[i].first>day)break; if(niza[i].first+d<day)return false; ress[day].push_back(niza[i].second); i++; } } return (i>=m); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>d>>m; for(int i=0; i<m; i++) { cin>>niza[i].first; niza[i].second=i+1; } sort(niza,niza+m); int b=0,e=m; int res=0; while(b<e) { int mid=(b+e)/2; bool flag=work(mid); if(flag) { res=mid; e=mid; } else b=mid+1; } cout<<res<<endl; work(res); for(int i=1; i<=n; i++) { for(auto x:ress[i])cout<<x<<" "; cout<<0<<endl; } return 0; } /* 8 2 12 1 2 4 2 1 3 5 6 2 3 6 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...