Submission #724985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
724985	2023-04-16T12:13:15 Z	Hectorungo_18	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	353 ms	13804 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	1620 KB	Output is correct
2	Correct	29 ms	1708 KB	Output is correct
3	Correct	28 ms	1636 KB	Output is correct
4	Correct	33 ms	1712 KB	Output is correct
5	Correct	36 ms	1620 KB	Output is correct
6	Correct	30 ms	1656 KB	Output is correct
7	Correct	33 ms	1620 KB	Output is correct
8	Correct	28 ms	1628 KB	Output is correct
9	Correct	146 ms	2012 KB	Output is correct
10	Correct	138 ms	1852 KB	Output is correct
11	Correct	24 ms	1636 KB	Output is correct
12	Correct	56 ms	3156 KB	Output is correct
13	Correct	77 ms	4592 KB	Output is correct
14	Correct	104 ms	6092 KB	Output is correct
15	Correct	135 ms	7568 KB	Output is correct
16	Correct	159 ms	9148 KB	Output is correct
17	Correct	188 ms	10592 KB	Output is correct
18	Correct	212 ms	12072 KB	Output is correct
19	Correct	353 ms	13804 KB	Output is correct
20	Correct	195 ms	10576 KB	Output is correct