Submission #668227

#	Time	Username	Problem	Language	Result	Execution time	Memory
668227		600Mihnea	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	237 ms	17080 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int main()
{
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#endif // ONPC

#ifndef ONPC
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  int span, delay, n;
  cin >> span >> delay >> n;
  vector<int> when(n), ord(n);
  for (int i = 0; i < n; i++)
  {
    cin >> when[i];
    ord[i] = i;
  }
  sort(ord.begin(), ord.end(), [&] (int i, int j) { return when[i] < when[j];});
  auto is_ok = [&] (int num_workers)
  {
    int position = 0;
    for (int day = 1; day <= span; day++)
    {
      int did_on_this_day = 0;
      while (did_on_this_day < num_workers && position < n)
      {
        int cand = when[ord[position]];
        if (day < cand)
        {
          break;
        }
        if (day > cand + delay)
        {
          return false;
        }
        position++;
        did_on_this_day++;
      }
    }
    return (position == n);
  };
  int low = 1, high = n, sol = -1;
  while (low <= high)
  {
    int mid = (low + high) / 2;
    if (is_ok(mid))
    {
      sol = mid;
      high = mid - 1;
    }
    else
    {
      low = mid + 1;
    }
  }
  assert(sol != -1);
  cout << sol << "\n";
  int num_workers = sol;
  int position = 0;
  for (int day = 1; day <= span; day++)
  {
    int did_on_this_day = 0;
    while (did_on_this_day < num_workers && position < n)
    {
      int cand = when[ord[position]];
      if (day < cand)
      {
        break;
      }
      if (day > cand + delay)
      {
        return false;
      }
      cout << ord[position] + 1 << " ";
      position++;
    }
    cout << "0\n";
  }
  assert(position == n);
  return 0;
}

• Subtask 1: 100 / 100