oj.uz

Submission #439749

# Submission time Handle Problem Language Result Execution time Memory
439749 2021-06-30T18:54:25 Z xz56 Job Scheduling (CEOI12_jobs) C++17
30 / 100
 540 ms 31240 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 +1 > 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
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 4488 KB Output isn't correct
2 Incorrect 61 ms 4460 KB Output isn't correct
3 Incorrect 64 ms 4468 KB Output isn't correct
4 Incorrect 56 ms 4564 KB Output isn't correct
5 Incorrect 58 ms 4464 KB Output isn't correct
6 Incorrect 60 ms 4460 KB Output isn't correct
7 Incorrect 56 ms 4480 KB Output isn't correct
8 Incorrect 60 ms 4476 KB Output isn't correct
9 Incorrect 69 ms 5856 KB Output isn't correct
10 Incorrect 75 ms 5876 KB Output isn't correct
11 Correct 64 ms 3396 KB Output is correct
12 Incorrect 119 ms 6696 KB Output isn't correct
13 Correct 190 ms 10740 KB Output is correct
14 Incorrect 287 ms 14616 KB Output isn't correct
15 Incorrect 296 ms 16660 KB Output isn't correct
16 Correct 418 ms 21088 KB Output is correct
17 Correct 484 ms 26336 KB Output is correct
18 Correct 487 ms 26724 KB Output is correct
19 Incorrect 540 ms 31240 KB Output isn't correct
20 Correct 491 ms 26344 KB Output is correct