Submission #439746

#	Time	Username	Problem	Language	Result	Execution time	Memory
439746		xz56	Job Scheduling (CEOI12_jobs)	C++17	61 / 100	546 ms	30276 KiB

jobs

/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ins insert
#define INF 1e18
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
// Author : Nav

ll n,d,m;
vector<pair<ll,ll>> req;
vector<vector<ll>> schedule;
bool check(ll machines){
  schedule.clear();
  schedule.resize(n+1);
  ll p = 0;
  for(ll i = 1;i<=n;i++){
    while(schedule[i].size() < machines && req[p].fi<=i && p<m){
      schedule[i].pb(req[p].se);
      if(i - req[p].fi > d) return false;
      p++;
    }
    // schedule[i].pb(0);
  }
  return true;
}
int main() {
  cin >> n >> d >> m;
  for(ll i = 0;i<m;i++){
    ll x; cin >> x;
    req.pb({x,i+1});
  }
  sort(req.begin(),req.end());
  schedule.resize(n+1);
  ll L = 1;
  ll R = 1e5;
  ll ans = 0;
  while(L<=R){
    ll mid = L + (R-L)/2;
    if(check(mid)){
      ans =mid;
      R = mid-1;
    }
    else {
      L = mid+1;
    }
  }
  cout << ans << '\n';
  for(ll i = 1;i<=n;i++){
    for(ll x : schedule[i]){
      cout << x << " ";
    }
    cout << 0 << '\n';
  }
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(ll)':
jobs.cpp:25:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   25 |     while(schedule[i].size() < machines && req[p].fi<=i && p<m){
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 61 / 100