제출 #1299474

#제출 시각아이디문제언어결과실행 시간메모리
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...