Submission #1256302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256302		lucaskojima	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	156 ms	26508 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 {
    queue<pii> q;
    vector<vector<int>> cur(n + 1);

    for (int i = 1; i <= n; i++) {
      for (int x : day[i])
        q.push({i, x});

      for (int _ = 0; _ < k; _++) {
        if (q.empty()) break;
        auto [x, id] = q.front();
        q.pop();

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

    res = cur;
    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: 100 / 100