Submission #1161817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161817		Marszpace	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	207 ms	21180 KiB

jobs

/*
 * And in that light, I find deliverance.
 * TASK : CEOI12 Jobs
 * AUTHOR : Marszpace
*/

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

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n,d,m;
  cin >> n >> d >> m;
  vector<pair<int,int>> a(m,{0,0});
  for(int i=0;i<m;i++){
    a[i].second=i;
    cin >> a[i].first;
  }
  sort(a.begin(),a.end());
  int l=1,r=1000005;
  while(r-l>1){
    int mid=(l+r)/2;
    queue<int> q;
    for(auto [tt,id]:a){
      q.push(tt);
    }
    bool can=true;
    for(int i=1;i<=n;i++){
      if(!q.empty() && q.front()+d<i){can=false;break;}
      int dd=0;
      while(!q.empty() && q.front()<=i && dd<mid){
        q.pop();dd++;
      }
    }
    if(can){
      r=mid;
    }
    else{
      l=mid;
    }
  }
  cout << r << "\n";


  queue<pair<int,int>> q;
  for(auto p:a){
    q.push(p);
  }
  bool can=true;
  for(int i=1;i<=n;i++){
    if(!q.empty() && q.front().first+d<i){can=false;break;}
    int dd=0;
    while(!q.empty() && q.front().first<=i && dd<r){
      cout << q.front().second+1 << " ";
      q.pop();dd++;
    }
    cout << "0\n";
  }
  return 0;
}

• Subtask 1: 100 / 100