Submission #936925

#	Time	Username	Problem	Language	Result	Execution time	Memory
936925		ventusliberum	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	115 ms	20624 KiB

jobs

/**
 *    title:  Job Scheduling
**/
#include <bits/stdc++.h>
using namespace std;

template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { auto sep = ""; for (auto &x : v) os << exchange(sep, " ") << x; return os; }
template <class T> vector<T> &operator+=(vector<T> &v, const T &a) { for (auto &x : v) x += a; return v; }
template <class T> vector<T> &operator-=(vector<T> &v, const T &a) { for (auto &x : v) x -= a; return v; }
template <class T, class U> inline bool chmax(T &a, const U &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return (b < a ? a = b, 1 : 0); }
#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
using ll = long long;
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N, D, M;
  cin >> N >> D >> M;
  vector<vector<int>> cn(N+1);
  for (int i = 0; i < M; i++) {
    int x;
    cin >> x;
    cn[x].push_back(i);
  }
  int l = 0, r = M + 1;
  auto valid = [&](int x) {
    int sum = 0;
    for (int i = 1; i <= N; i++) {
      if (si(cn[i])) {
        sum += si(cn[i]);
        if ((sum + x - 1) / x > D + 1) return false;
      }
      sum = max(0, sum - x);
    }
    return true;
  };
  while (l < r) {
    int mid = (l + r) / 2;
    valid(mid) ? r = mid : l = mid + 1;
  }

  cout << l << '\n';
  vector<int> use;
  int j = 0;
  for (int i = 1; i <= N; i++) {
    for (int x : cn[i]) {
      use.push_back(x);
    }
    vector<int> cur;
    for (int s = j; j < min(si(use), s + l); j++) {
      cur.push_back(use[j]);
    }
    cur += 1;
    cout << cur;
    if (si(cur)) cout << ' ';
    cout << 0 << '\n';
  }
}

• Subtask 1: 100 / 100