oj.uz

Submission #439746

# Submission time Handle Problem Language Result Execution time Memory
439746 2021-06-30T18:50:17 Z xz56 Job Scheduling (CEOI12_jobs) C++17
61 / 100
 546 ms 30276 KB 
/*
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

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

# Verdict Execution time Memory Grader output
1 Partially correct 47 ms 3892 KB Partially correct
2 Partially correct 49 ms 3964 KB Partially correct
3 Partially correct 54 ms 4032 KB Partially correct
4 Partially correct 57 ms 3928 KB Partially correct
5 Partially correct 49 ms 3932 KB Partially correct
6 Partially correct 49 ms 3936 KB Partially correct
7 Partially correct 49 ms 3888 KB Partially correct
8 Partially correct 59 ms 3888 KB Partially correct
9 Partially correct 72 ms 5872 KB Partially correct
10 Partially correct 71 ms 6084 KB Partially correct
11 Correct 60 ms 3400 KB Output is correct
12 Correct 139 ms 6740 KB Output is correct
13 Partially correct 180 ms 10908 KB Partially correct
14 Correct 283 ms 14616 KB Output is correct
15 Partially correct 275 ms 15388 KB Partially correct
16 Correct 424 ms 20996 KB Output is correct
17 Correct 499 ms 26464 KB Output is correct
18 Correct 492 ms 26796 KB Output is correct
19 Partially correct 546 ms 30276 KB Partially correct
20 Correct 536 ms 26344 KB Output is correct