Submission #417509

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
417509	2021-06-03T20:39:57 Z	jackkkk	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	303 ms	20696 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	2372 KB	Output is correct
2	Correct	25 ms	2404 KB	Output is correct
3	Correct	26 ms	2404 KB	Output is correct
4	Correct	25 ms	2404 KB	Output is correct
5	Correct	25 ms	2524 KB	Output is correct
6	Correct	25 ms	2532 KB	Output is correct
7	Correct	25 ms	2376 KB	Output is correct
8	Correct	25 ms	2408 KB	Output is correct
9	Correct	34 ms	2628 KB	Output is correct
10	Correct	35 ms	2640 KB	Output is correct
11	Correct	33 ms	2424 KB	Output is correct
12	Correct	64 ms	4676 KB	Output is correct
13	Correct	97 ms	6932 KB	Output is correct
14	Correct	136 ms	9268 KB	Output is correct
15	Correct	166 ms	11588 KB	Output is correct
16	Correct	201 ms	13808 KB	Output is correct
17	Correct	247 ms	16068 KB	Output is correct
18	Correct	267 ms	18352 KB	Output is correct
19	Correct	303 ms	20696 KB	Output is correct
20	Correct	252 ms	16104 KB	Output is correct