oj.uz

Submission #439742

# Submission time Handle Problem Language Result Execution time Memory
439742 2021-06-30T18:36:17 Z xz56 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 484 ms 16372 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

int n,d,m;
vector<pair<int,int>> req;
vector<vector<int>> schedule;
bool check(int machines){
  schedule.clear();
  schedule.resize(n+1);
  int p = 0;
  for(int i = 1;i<=n;i++){
    while(schedule[i].size() < machines && req[p].fi<=i && p<n){
      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(int i = 0;i<m;i++){
    int x; cin >> x;
    req.pb({x,i+1});
  }
  sort(req.begin(),req.end());
  schedule.resize(n+1);
  int L = 1;
  int R = m;
  int ans = 0;
  while(L<=R){
    int mid = L + (R-L)/2;
    if(check(mid)){
      ans =mid;
      R = mid-1;
    }
    else {
      L = mid+1;
    }
  }
  cout << L << '\n';
  for(int i = 1;i<=n;i++){
    for(int x : schedule[i]){
      cout << x << " ";
    }
    cout << '\n';
  }
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:25:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     while(schedule[i].size() < machines && req[p].fi<=i && p<n){
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:44:7: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   44 |   int ans = 0;
      |       ^~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 1956 KB Output isn't correct
2 Incorrect 48 ms 1940 KB Output isn't correct
3 Incorrect 45 ms 1976 KB Output isn't correct
4 Incorrect 43 ms 1928 KB Output isn't correct
5 Incorrect 35 ms 1972 KB Output isn't correct
6 Incorrect 34 ms 1964 KB Output isn't correct
7 Incorrect 49 ms 2000 KB Output isn't correct
8 Incorrect 36 ms 1952 KB Output isn't correct
9 Incorrect 127 ms 7472 KB Expected EOLN
10 Incorrect 112 ms 7344 KB Expected EOLN
11 Incorrect 39 ms 1732 KB Output isn't correct
12 Incorrect 77 ms 3136 KB Output isn't correct
13 Incorrect 118 ms 5536 KB Output isn't correct
14 Incorrect 174 ms 5964 KB Output isn't correct
15 Incorrect 190 ms 6184 KB Output isn't correct
16 Incorrect 262 ms 11096 KB Output isn't correct
17 Incorrect 299 ms 11252 KB Output isn't correct
18 Incorrect 319 ms 10744 KB Output isn't correct
19 Incorrect 484 ms 16372 KB Output isn't correct
20 Incorrect 319 ms 11112 KB Output isn't correct