oj.uz

Submission #439777

# Submission time Handle Problem Language Result Execution time Memory
439777 2021-06-30T19:12:03 Z xz56 Job Scheduling (CEOI12_jobs) C++17
48 / 100
 617 ms 31200 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  > d + req[p].fi) 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
48.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4084 KB Output is correct
2 Correct 63 ms 4092 KB Output is correct
3 Correct 53 ms 4096 KB Output is correct
4 Correct 52 ms 3968 KB Output is correct
5 Correct 54 ms 4148 KB Output is correct
6 Correct 52 ms 4064 KB Output is correct
7 Correct 53 ms 4016 KB Output is correct
8 Correct 52 ms 4112 KB Output is correct
9 Incorrect 75 ms 5956 KB Output isn't correct
10 Partially correct 81 ms 6028 KB Partially correct
11 Incorrect 61 ms 3388 KB Output isn't correct
12 Incorrect 148 ms 6656 KB Output isn't correct
13 Partially correct 183 ms 10584 KB Partially correct
14 Incorrect 282 ms 14036 KB Output isn't correct
15 Incorrect 308 ms 15764 KB Output isn't correct
16 Partially correct 359 ms 16788 KB Partially correct
17 Incorrect 567 ms 26360 KB Output isn't correct
18 Partially correct 481 ms 26288 KB Partially correct
19 Incorrect 617 ms 31200 KB Output isn't correct
20 Incorrect 553 ms 26420 KB Output isn't correct