Submission #439745

#	Time	Username	Problem	Language	Result	Execution time	Memory
439745		xz56	Job Scheduling (CEOI12_jobs)	C++17	58 / 100	540 ms	19148 KiB

jobs

/*
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 << 0 << '\n';
  }
}

Compilation message (stderr)

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: 58 / 100