oj.uz

Submission #462279

# Submission time Handle Problem Language Result Execution time Memory
462279 2021-08-10T09:51:27 Z dqk Job Scheduling (CEOI12_jobs) C++17
75 / 100
 978 ms 56824 KB 
 #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

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

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6644 KB Output is correct
2 Correct 35 ms 6596 KB Output is correct
3 Correct 43 ms 6604 KB Output is correct
4 Correct 34 ms 6600 KB Output is correct
5 Correct 36 ms 6664 KB Output is correct
6 Correct 33 ms 6600 KB Output is correct
7 Correct 35 ms 6600 KB Output is correct
8 Correct 33 ms 6596 KB Output is correct
9 Correct 61 ms 6804 KB Output is correct
10 Correct 63 ms 6816 KB Output is correct
11 Correct 82 ms 6672 KB Output is correct
12 Correct 172 ms 13188 KB Output is correct
13 Correct 277 ms 19224 KB Output is correct
14 Correct 371 ms 25668 KB Output is correct
15 Correct 507 ms 31848 KB Output is correct
16 Runtime error 578 ms 38216 KB Memory limit exceeded
17 Runtime error 736 ms 44268 KB Memory limit exceeded
18 Runtime error 859 ms 50452 KB Memory limit exceeded
19 Runtime error 978 ms 56824 KB Memory limit exceeded
20 Runtime error 700 ms 44208 KB Memory limit exceeded