Submission #724985

#	Time	Username	Problem	Language	Result	Execution time	Memory
724985		Hectorungo_18	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	353 ms	13804 KiB

jobs

#include <algorithm>
#include <iostream>
#include <map>
#include<queue>
#include<set>
#include <vector>
 
using namespace std;
 
// #define int long long int
 
#define vvi vector<vector<int>>
#define vi vector<int>
#define s second
#define f first
 
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, d, me;
  cin >> n >> d >> me;
  vector<pair<int, int>> v(me);
  for(int i = 0; i < me; i++){
    cin >> v[i].f;
    v[i].s = i+1;
  }
  int l = 0, r = me;
  sort(v.begin(), v.end());
  int ans = r;
  while(l < r){
    int m = (l+r+1)/2;
    int cur = 1, sol = 0, aux = 0;
    bool p = 1;
    for(int i = 0; i < me; i++){
      if(v[i].f > cur){
        cur=v[i].f;
        aux=0;
      }
      if(v[i].f+d < cur) p = 0;
      aux++;
      if(aux == m){
        aux = 0;
        cur++;
      }
      // cout << v[i].f << " " << d << " " << cur << endl;
      
      if(!p) break;
    }  
    if(p){
      sol=m;
      ans = m;
      r = m-1;
    }
    else l = m;
    // if(p) ans = min(ans, sol);
    // cout << l << " " << m << endl;
  }
  cout << ans << endl;
  int cur = 0, aux = 1, day = 1, tot = 0;
  int j = 0;
  for(int i = 0; i < n;){
    if(j == me){
      cout << 0 << endl;
      i++;
      continue;
    }
    if(day < v[j].f){
      day++;
      cout << 0 << endl;
      aux++;
      cur = 0;
      i++;
      continue;
    }
    
    if(cur == 0) aux++;
    // cout << v[i].s << " ";
    cout << v[j].s <<  " ";
    j++;
    tot++;
    cur++;
    if(cur == ans) {
      cout << 0 << "\n";
      cur = 0;
      day++;
      i++;
    }
    
  }
  // if(cur == 0) aux++;
  // for(int i = aux; i <= n; i++) cout << 0 << "\n";
  return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:32:18: warning: variable 'sol' set but not used [-Wunused-but-set-variable]
   32 |     int cur = 1, sol = 0, aux = 0;
      |                  ^~~

• Subtask 1: 100 / 100