Submission #462493

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
462493	2021-08-10T16:09:04 Z	dqk	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	215 ms	14636 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1924 KB	Output is correct
2	Correct	19 ms	1956 KB	Output is correct
3	Correct	19 ms	1988 KB	Output is correct
4	Correct	19 ms	1948 KB	Output is correct
5	Correct	19 ms	1976 KB	Output is correct
6	Correct	24 ms	1916 KB	Output is correct
7	Correct	19 ms	1892 KB	Output is correct
8	Correct	19 ms	1944 KB	Output is correct
9	Correct	29 ms	4728 KB	Output is correct
10	Correct	39 ms	4688 KB	Output is correct
11	Correct	26 ms	1868 KB	Output is correct
12	Correct	42 ms	3284 KB	Output is correct
13	Correct	72 ms	5100 KB	Output is correct
14	Correct	91 ms	6564 KB	Output is correct
15	Correct	100 ms	7496 KB	Output is correct
16	Correct	173 ms	9544 KB	Output is correct
17	Correct	194 ms	11308 KB	Output is correct
18	Correct	162 ms	11428 KB	Output is correct
19	Correct	215 ms	14636 KB	Output is correct
20	Correct	174 ms	11376 KB	Output is correct