Submission #417509

#	Time	Username	Problem	Language	Result	Execution time	Memory
417509		jackkkk	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	303 ms	20696 KiB

jobs

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>

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){
  int curr_day = 1;
  int num_used = 0;
  long long curr_request = 0;
  while(curr_request < (int) requests.size()){
    if(requests[curr_request].first>curr_day){
      curr_day++;
      num_used=0;
      continue;
    }
    if(curr_day-requests[curr_request].first>d){
      return false;
    }
    num_used++;
    if(num_used==machines){
      curr_day++;
      num_used=0;
    }
    curr_request++;
  }
  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 = 1000000;
  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: 100 / 100