Submission #1299474

#TimeUsernameProblemLanguageResultExecution timeMemory
1299474algorubikJob Scheduling (CEOI12_jobs)C++20
90 / 100
245 ms36832 KiB
#include <bits/stdc++.h> using namespace std; #define fo(i, n) for (ll i = 0; i < n; i++) #define Fo(i, k, n) for (ll i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1) #define ll long long #define pb push_back #define F first #define S second #define yes cout<<'Y'<<'E'<<'S'<<endl; #define no cout<<'N'<<'O'<<endl; typedef vector<long long> vll; const ll MOD = 1e9 + 7; void solve(){ ll n,d,m;cin>>n>>d>>m; map<ll,vll> mm; vector<pair<ll,ll>> v; fo(i,m){ ll x;cin>>x; v.pb({x,i}); } sort(v.begin(),v.end()); ll r = 1; ll e = 1e6; ll ans = 0; while(r<=e){ ll mid = (r+e)/2; ll i = 0; ll curday = 1; bool check = 1; ll current_work = mid; while(i!=m && curday<=n){ if(i<m && current_work>0 && v[i].F<=curday){ current_work--; if(curday-v[i].F>d){ check = 0; break; } i++; } if(current_work==0){ curday++; current_work = mid; } if(v[i].F>curday){ current_work = mid; curday++; } } if(check){ ans = mid; e = mid - 1; } else{ r = mid + 1; } } ll curday = 1; ll i = 0; ll current_work = ans; while(i!=m && curday<=n){ if(i<m && current_work>0 && v[i].F<=curday){ current_work--; mm[curday].pb(v[i].S+1); i++; } if(current_work==0){ curday++; current_work = ans; } if(v[i].F>curday){ current_work = ans; curday++; } } cout<<ans<<"\n"; fo(i,n){ for(auto x:mm[i+1]){ cout<<x<<" "; }cout<<0<<"\n"; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll test; test = 1; // cin >> test; while (test--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...