oj.uz

Submission #439758

# Submission time Handle Problem Language Result Execution time Memory
439758 2021-06-30T19:02:28 Z xz56 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 358 ms 16816 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(req[p].fi + d > i) 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;
  while(L<=R){
    ll mid = L + (R-L)/2;
    if(check(mid)){
      R = mid-1;
    }
    else {
      L = mid+1;
    }
  }
  cout << L << '\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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 2368 KB Output isn't correct
2 Incorrect 27 ms 2456 KB Output isn't correct
3 Incorrect 33 ms 2388 KB Output isn't correct
4 Incorrect 28 ms 2448 KB Output isn't correct
5 Incorrect 29 ms 2368 KB Output isn't correct
6 Incorrect 27 ms 2364 KB Output isn't correct
7 Incorrect 27 ms 2480 KB Output isn't correct
8 Incorrect 28 ms 2368 KB Output isn't correct
9 Incorrect 49 ms 4416 KB Output isn't correct
10 Incorrect 50 ms 4404 KB Output isn't correct
11 Incorrect 38 ms 2420 KB Output isn't correct
12 Incorrect 75 ms 4520 KB Output isn't correct
13 Incorrect 115 ms 8616 KB Output isn't correct
14 Incorrect 173 ms 8596 KB Output isn't correct
15 Incorrect 190 ms 8616 KB Output isn't correct
16 Incorrect 250 ms 16740 KB Output isn't correct
17 Incorrect 293 ms 16756 KB Output isn't correct
18 Incorrect 308 ms 16780 KB Output isn't correct
19 Incorrect 358 ms 16816 KB Output isn't correct
20 Incorrect 346 ms 16796 KB Output isn't correct