oj.uz

Submission #439743

# Submission time Handle Problem Language Result Execution time Memory
439743 2021-06-30T18:43:09 Z xz56 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 639 ms 22172 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<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(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<m){
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
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 47 ms 2548 KB Expected EOLN
2 Incorrect 47 ms 2600 KB Expected EOLN
3 Incorrect 48 ms 2652 KB Expected EOLN
4 Incorrect 57 ms 2576 KB Expected EOLN
5 Incorrect 50 ms 2616 KB Expected EOLN
6 Incorrect 47 ms 2540 KB Expected EOLN
7 Incorrect 48 ms 2664 KB Expected EOLN
8 Incorrect 56 ms 2524 KB Expected EOLN
9 Incorrect 140 ms 7192 KB Expected EOLN
10 Incorrect 111 ms 7156 KB Expected EOLN
11 Incorrect 60 ms 2168 KB Expected EOLN
12 Incorrect 130 ms 4144 KB Expected EOLN
13 Incorrect 186 ms 6600 KB Expected EOLN
14 Incorrect 285 ms 9000 KB Expected EOLN
15 Incorrect 296 ms 10512 KB Expected EOLN
16 Incorrect 433 ms 12920 KB Expected EOLN
17 Incorrect 497 ms 16004 KB Expected EOLN
18 Incorrect 518 ms 16648 KB Expected EOLN
19 Incorrect 639 ms 22172 KB Expected EOLN
20 Incorrect 513 ms 15932 KB Expected EOLN