제출 #455180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
455180		inluminas	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	258 ms	20560 KiB

jobs

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)

const int lmt=1e5+10;
vector<int>adj[lmt],res[lmt];
int n,d,m,cnt[lmt];

int main(){
  fastio;

  cin>>n>>d>>m;
  for(int i=1;i<=m;i++){
    int a;
    cin>>a;
    adj[a].push_back(i);
    cnt[a]++;
  }
  int lo=1,hi=m;
  while(lo<hi){
    int mid=(lo+hi)>>1,ache[lmt]={0},cur=1,bad=0;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=cnt[i];j++){
        while(cur<i || ache[cur]==mid) cur++;
        if(cur-i>d){
          bad=1;
          break;
        }
        ache[cur]++;
      }
      if(bad) break;
    }
    if(bad) lo=mid+1;
    else hi=mid;
  }
  int ache[lmt]={0},cur=1;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=cnt[i];j++){
      while(cur<i || ache[cur]==lo) cur++;
      ache[cur]++;
      res[cur].push_back(adj[i][j-1]);
    }
  }
  cout<<lo<<endl;
  for(int i=1;i<=n;i++){
    for(int v:res[i]) cout<<v<<" ";
    cout<<0<<endl;
  }
}

• Subtask 1: 100 / 100