Submission #462305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
462305	2021-08-10T10:42:01 Z	dqk	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	1000 ms	56032 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(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 = 1e9;
      while (lo < hi) {
          int mi = (lo + hi) / 2;
          int task = 0;
          bool ok = true;
          for (int i = 1; i <= N && ok; ++i) {
              int cur = 0;
              if (task < M && i > a[task][0] + D)
                  ok = false;
              while (task < M && i >= a[task][0] && i <= a[task][0] + D && cur < mi) {
                  task++; cur++;
              }
          }
          if (task == M && ok)
              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;
 }

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	6344 KB	Output is correct
2	Correct	35 ms	6308 KB	Output is correct
3	Correct	36 ms	6336 KB	Output is correct
4	Correct	36 ms	6316 KB	Output is correct
5	Correct	36 ms	6340 KB	Output is correct
6	Correct	47 ms	6296 KB	Output is correct
7	Correct	35 ms	6312 KB	Output is correct
8	Correct	40 ms	6316 KB	Output is correct
9	Correct	65 ms	6520 KB	Output is correct
10	Correct	65 ms	6560 KB	Output is correct
11	Correct	55 ms	6300 KB	Output is correct
12	Correct	163 ms	12512 KB	Output is correct
13	Correct	297 ms	18672 KB	Output is correct
14	Correct	438 ms	24928 KB	Output is correct
15	Correct	545 ms	31032 KB	Output is correct
16	Runtime error	733 ms	37280 KB	Memory limit exceeded
17	Runtime error	907 ms	43436 KB	Memory limit exceeded
18	Runtime error	930 ms	49640 KB	Memory limit exceeded
19	Execution timed out	1079 ms	56032 KB	Time limit exceeded
20	Runtime error	821 ms	43428 KB	Memory limit exceeded