oj.uz

Submission #439751

# Submission time Handle Problem Language Result Execution time Memory
439751 2021-06-30T18:57:09 Z xz56 Job Scheduling (CEOI12_jobs) C++17
64 / 100
 555 ms 31316 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 = 1e6;
  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
64.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 55 ms 4088 KB Partially correct
2 Partially correct 54 ms 3984 KB Partially correct
3 Partially correct 52 ms 4004 KB Partially correct
4 Partially correct 52 ms 4096 KB Partially correct
5 Partially correct 53 ms 4020 KB Partially correct
6 Partially correct 53 ms 3980 KB Partially correct
7 Partially correct 52 ms 4084 KB Partially correct
8 Partially correct 52 ms 4032 KB Partially correct
9 Correct 74 ms 5948 KB Output is correct
10 Partially correct 79 ms 6128 KB Partially correct
11 Correct 62 ms 3428 KB Output is correct
12 Correct 125 ms 6680 KB Output is correct
13 Partially correct 191 ms 10908 KB Partially correct
14 Correct 297 ms 14620 KB Output is correct
15 Correct 307 ms 17180 KB Output is correct
16 Partially correct 362 ms 16988 KB Partially correct
17 Correct 555 ms 26344 KB Output is correct
18 Partially correct 490 ms 26800 KB Partially correct
19 Correct 555 ms 31316 KB Output is correct
20 Correct 544 ms 26364 KB Output is correct