Submission #999557

#	Time	Username	Problem	Language	Result	Execution time	Memory
999557		m_bezrutchka	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	140 ms	5904 KiB

jobs

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

const int MAXN = 1e5 + 10;

int n, d, m;
pair<int, int> requests[10*MAXN];
vector <int> resp[MAXN];

bool possible(int k) {
  if (k <= 0) return false;
  if (k >= m) return true;
  int pos = 0;
  for (int day = 1; day <= n; day++) {
    resp[day].clear();
    for (int j = 0; j < k; j++) {
      if (pos >= m) break;
      int day_pos = requests[pos].first;
      int idx_pos = requests[pos].second;
      if (day_pos > day) break;
      if (day_pos + d < day) return false;
      resp[day].push_back(idx_pos);
      pos++;
    }
  }
  return (pos >= m);
}

int b_search() {
  int l = 0, r = m;
  while (l < r) {
    int mid = (l + r) / 2;
    if (possible(mid)) r = mid;
    else l = mid + 1;
  }
  return r;
}

int main() {
  cin >> n >> d >> m;
  if (m > (int)1e5) return 0;
  int x;
  for (int i = 0; i < m; i++) {
    cin >> x;
    requests[i] = {x, i + 1};
  }
  sort(requests, requests + m);
  int ans = b_search();
  cout << ans << endl;
  
  possible(ans);
  for (int i = 1; i <= n; i++) {
    for (int x : resp[i]) cout << x << " ";
    cout << 0 << endl;
  }
  return 0;
}

• Subtask 1: 55 / 100