Submission #417498

#	Time	Username	Problem	Language	Result	Execution time	Memory
417498		jackkkk	Job Scheduling (CEOI12_jobs)	C++11	55 / 100	580 ms	21444 KiB

jobs

#include <bits/stdc++.h>
 
using namespace std;
 
 
void quit() {
  cout.flush();
  exit(0);
}
long long n, d, m;
vector <pair<long long ,long long>> requests;
 
bool good(long long machines){
  for(long long i = 0; i < m; i++){
    if((i/machines+1)-requests[i].first>d){
      return false;
    }
  }
  return true;
}
 
 
 
int main(void){
  //freopen("qwer.in", "r", stdin);
  //freopen("qwer.out", "w", stdout);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> d >> m;
  requests.resize(m);
  for(long long i = 0; i < m; i++){
    cin >> requests[i].first;
    requests[i].second = i+1;
  }
  sort(requests.begin(), requests.end());
  
  long long s = 0, e = LLONG_MAX/2;
  while(s!=e){
    long long mid = (s+e)/2;
    if(good(mid)){
      e=mid;
    }
    else{
      s=mid+1;
    }
  }
  cout << e << "\n";
  long long num_left = n;
  for(long long i = 0; i < m; i+=e){
    for(long long j = i; j < min(m, i+e); j++){
      cout << requests[j].second << " ";
    }
    num_left--;
    cout << "0\n";
  }
  for(long long i = 0; i < num_left; i++){
    cout << "0\n";
  }
  quit();
}

• Subtask 1: 55 / 100