Submission #462478

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
462478	2021-08-10T16:02:32 Z	dqk	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	192 ms	14276 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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1860 KB	Output is correct
2	Correct	19 ms	1836 KB	Output is correct
3	Correct	19 ms	1852 KB	Output is correct
4	Correct	19 ms	1868 KB	Output is correct
5	Correct	20 ms	1972 KB	Output is correct
6	Correct	19 ms	1868 KB	Output is correct
7	Correct	24 ms	1900 KB	Output is correct
8	Correct	19 ms	1852 KB	Output is correct
9	Correct	28 ms	4728 KB	Output is correct
10	Correct	28 ms	4696 KB	Output is correct
11	Incorrect	25 ms	1748 KB	Output isn't correct
12	Correct	39 ms	3016 KB	Output is correct
13	Correct	59 ms	4896 KB	Output is correct
14	Correct	94 ms	6212 KB	Output is correct
15	Incorrect	93 ms	7040 KB	Output isn't correct
16	Correct	133 ms	9064 KB	Output is correct
17	Correct	153 ms	10844 KB	Output is correct
18	Correct	152 ms	10948 KB	Output is correct
19	Correct	192 ms	14276 KB	Output is correct
20	Correct	166 ms	10940 KB	Output is correct