Submission #462293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
462293	2021-08-10T10:14:10 Z	dqk	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	1000 ms	56148 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 = M;
      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	6340 KB	Output is correct
2	Correct	32 ms	6312 KB	Output is correct
3	Correct	33 ms	6352 KB	Output is correct
4	Correct	33 ms	6280 KB	Output is correct
5	Correct	36 ms	6376 KB	Output is correct
6	Correct	33 ms	6432 KB	Output is correct
7	Correct	33 ms	6308 KB	Output is correct
8	Correct	33 ms	6300 KB	Output is correct
9	Correct	62 ms	6468 KB	Output is correct
10	Correct	57 ms	6468 KB	Output is correct
11	Correct	62 ms	6308 KB	Output is correct
12	Correct	176 ms	12556 KB	Output is correct
13	Correct	268 ms	18668 KB	Output is correct
14	Correct	401 ms	25004 KB	Output is correct
15	Correct	484 ms	31028 KB	Output is correct
16	Runtime error	594 ms	37352 KB	Memory limit exceeded
17	Runtime error	773 ms	43444 KB	Memory limit exceeded
18	Runtime error	872 ms	49644 KB	Memory limit exceeded
19	Execution timed out	1002 ms	56148 KB	Time limit exceeded
20	Runtime error	709 ms	43556 KB	Memory limit exceeded