제출 #1272718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272718		desmond1015	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	172 ms	13876 KiB

jobs

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

#define ll long long

int MOD = 1e9+7;
int INF = 1e9;

void solve() {
  int n, d, m;
  cin >> n >> d >> m;
  vector<array<int, 2>> r(m);
  for (int i = 0; i < m; i++) {
    cin >> r[i][0];
    r[i][1] = i;
  }
  sort(r.begin(), r.end());
  int lo = 1, hi = m;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    int idx = 0;
    bool ok = true;
    for (int t = 1; t <= n; t++) {
      int i = 0;
      while (i < mid && idx + i < m) {
        if (r[idx + i][0] > t) {
          break;
        }
        if (r[idx + i][0] + d < t) {
          ok = false;
          goto outer;
        }
        i++;
      }
      idx += i;
      if (idx >= m) {
        break;
      }
    }
    outer:;
    if (ok) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  cout << lo << '\n';
  int idx = 0;
  for (int t = 1; t <= n; t++) {
    int i = 0;
    while (i < lo && idx + i < m) {
      if (r[idx + i][0] > t) {
        break;
      }
      cout << r[idx + i][1] + 1 << ' ';
      i++;
    }
    idx += i;
    cout << "0\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);

  // freopen("input.in", "r", stdin);
  // freopen("output.out", "w", stdout);

  // int T = 1;
  // cin >> T;
  // while (T--) {
    solve();
  // }

  return 0;
}

• Subtask 1: 100 / 100