Submission #1256299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256299		lucaskojima	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	1096 ms	13380 KiB

jobs

#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n, d, m; cin >> n >> d >> m;

  vector<vector<int>> day(n + 1);
  for (int i = 1; i <= m; i++) {
    int x; cin >> x;
    day[x].push_back(i);
  }

  vector<vector<int>> res(n + 1);

  auto val = [&](int k) -> bool {
    for (int i = 1; i <= n; i++) // clear
      res[i].clear();

    set<pii> st;
    for (int i = 1; i <= n; i++) {
      for (int x : day[i])
        st.insert({i, x});

      for (int _ = 0; _ < k; _++) {
        if (st.empty()) continue;
        auto [x, id] = *st.begin();
        st.erase(st.begin());

        if (x + d < i) return false;
        res[i].push_back(id);
      }
    }
    return true;
  };

  int l = 0; // l is bad
  int r = m; // r is good
  while (r > l + 1) {
    int mid = (l + r) / 2;
    val(mid) ? r = mid : l = mid;
  }

  cout << r << nl;
  for (int i = 1; i <= n; i++) {
    for (int x : res[i])
      cout << x << ' ';
    cout << 0 << nl;
  }
  return 0;
}

• Subtask 1: 60 / 100