Submission #462493

#	Time	Username	Problem	Language	Result	Execution time	Memory
462493		dqk	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	215 ms	14636 KiB

jobs

#include <bits/stdc++.h>
 
 int main() {
     std::ios_base::sync_with_stdio(false);
     std::cin.tie(nullptr);
     int N, D, M;
      std::cin >> N >> D >> M;
      std::vector<std::vector<int>> a(N + 1);
      for (int i = 0; i < M; ++i) {
          int x;
          std::cin >> x;
          a[x].push_back(i + 1);
      }
      int lo = 1, hi = M;
      while (lo < hi) {
          int mi = (lo + hi) / 2;
          std::vector<int> b(N + 1, 0);         
for (int i = 1; i <= N; ++i) {
              b[i] = a[i].size();
          }
          bool ok = true;
          for (int i = 1, j = 1; i <= N && ok; ++i) {
              int tot = 0;
              while (tot < mi && j < N && ok) {
                  if (j + D < i && b[j] > 0)
                      ok = false;
                  else if (i >= j && j + D >= i) {
                      if (tot + b[j] <= mi) {
                          tot += b[j];
                          j++;
                      }
                      else {
                          b[j] -= mi - tot;
                          tot = mi;
                      }
                  }
                  else
                      break;
              }
          }
          if (ok)
              hi = mi;
          else
              lo = mi + 1;
      }
      std::cout << lo << "\n";
      for (int i = 1, j = 1, k = 0; i <= N; ++i) {
          for (int l = 0; l < lo && i >= j;) {
              if (k >= a[j].size()) {
                  k = 0;
                  j++;
              }
              else {
                  std::cout << a[j][k] << " ";
                  k++;
                  l++;
              }
          }
          std::cout << "0\n";
      }
      return 0;
 }

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |               if (k >= a[j].size()) {
      |                   ~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100