제출 #1258197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258197		hawashra	Job Scheduling (CEOI12_jobs)	C++20	4 / 100	1097 ms	34752 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define vll vector<long long>

constexpr int MOD = 1'000'000'007;

#define endl '\n'
#define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr);
#define ALL(x) begin(x), end(x)

#define ll long long
#define ull unsigned long long
#define lld long double

template <typename T = int>
istream &operator>>(istream &in, vector<T> &v) {
  for (auto &x : v) in >> x;
  return in;
}

template <typename T = int>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (const T &x : v) out << x << ' ';
  return out;
}

inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
inline void inc(int& a, int b) { a = add(a, b); }
inline int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
inline void dec(int& a, int b) { a = sub(a, b); }


#ifdef LOCAL
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif


void solve() {
  int n, d, m; cin >> n >> d >> m;
  vii jobs(m);
  for (int i = 1; i <= m; i++){
    jobs[i].second = i;
    cin >> jobs[i].first;
  }

  int l = 1, r = m;
  int ans = m;
  sort(ALL(jobs));
  vector<vi> dist(n);

  auto ok = [&](int mid){
    multiset<int> availableTimes;
    for (int i = 0; i < n; i++){
      dist[i].clear();
    }
    for (int i = 0; i < mid; i++){
      availableTimes.insert(0);
    }
    for (auto ti : jobs){
      auto it = availableTimes.begin();
      if (*it + 1 > ti.first + d || *it + 1 >= n){
        return false;
      }
      availableTimes.insert(max(ti.first + 1, *it + 1));
      dist[max(ti.first, *it)].push_back(ti.second);
      availableTimes.extract(*it);
    }
    return true;
  };

  while(l <= r){
    int mid = (l + r) / 2;
    if (ok(mid)){
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  cout << ans << endl;
  for (int i =0; i < n; i++){
    for (int j = 0; j < dist[i].size(); j++){
      cout << dist[i][j] + 1 << ' ';
    }
    cout << "0\n";
  }
}

int main() {
  FAST

  int tt=1;
  while (tt --> 0) {
    solve();
  }
}

• Subtask 1: 4 / 100