Submission #462279

#	Time	Username	Problem	Language	Result	Execution time	Memory
462279		dqk	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	978 ms	56824 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(M, std::vector<int>(2));
      for (int i = 0; i < M; ++i) {
          std::cin >> a[i][0];
          a[i][1] = i + 1;
      }
      sort(a.begin(), a.end());
      int lo = 1, hi = M;
      while (lo < hi) {
          int mi = (lo + hi) / 2;
          int task = 0;
          bool ok = true;
          for (int i = 1; i <= N; ++i) {
              int cur = 0;
              while (task < M && i >= a[task][0] && i <= a[task][0] + D && cur < mi) {
                  task++; cur++;
              }
          }
          if (task == M)
              hi = mi;
          else
              lo = mi + 1;
      }
      std::cout << lo << "\n";
      int task = 0;
      for (int i = 1; i <= N; ++i) {
          int cur = 0;
          while (task < M && i >= a[task][0] && i <= a[task][0] + D && cur < lo) {
              std::cout << a[task][1] << " ";
              task++, cur++;
          }
          std::cout << 0 << "\n";
      }
      return 0;
  }   

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:18:16: warning: unused variable 'ok' [-Wunused-variable]
   18 |           bool ok = true;
      |                ^~

• Subtask 1: 75 / 100