제출 #1358731

#제출 시각아이디문제언어결과실행 시간메모리
1358731jumpJob Scheduling (CEOI12_jobs)C++20
100 / 100
54 ms15592 KiB
#include <bits/stdc++.h>
#define int long long
int n,d,m;
int jobs[100010];
std::vector<int> jobV[100010];
bool solve(int amt){
  std::queue<std::pair<int,int>> q;
  for(int i=1;i<=n;i++){
    //std::cout << amt << ' ' << i << '\n';
    if(jobs[i]!=0)
    q.push({i,jobs[i]});
    int left = amt;
    if(!q.empty()&&i-d>q.front().first)return false;
    while(!q.empty()&&q.front().second<=left)left-=q.front().second,q.pop();
    if(!q.empty()&&q.front().second>left)q.front().second-=left;
  }
  return true;
}
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> d >> m;
  for(int i=1;i<=m;i++){
    int day;
    std::cin >> day;
    jobs[day]+=1;
    jobV[day].push_back(i);
  }
  int l=0,r=m;
  while(l<r){
    int mid = (l+r)/2;
    if(solve(mid)){
      r=mid;
    }
    else{
      l=mid+1;
    }
  }
  std::cout << r << '\n';
  std::queue<int> q;
  for(int i=1;i<=n;i++){
    while(jobV[i].size()>0)
    q.push(jobV[i].back()),jobV[i].pop_back();
    int left = r;
    while(!q.empty()&&left>0)std::cout << q.front() << ' ',q.pop(),left-=1;
    std::cout << 0 << '\n';
  }
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4 
*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…