Submission #462303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
462303	2021-08-10T10:41:14 Z	dqk	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	851 ms	59476 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());
      std::vector<int> b(M);
      for (int i = 0; i < a.size(); ++i)
          b[i] = a[i][0];
      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 u = std::upper_bound(b.begin(), b.end(), i) - b.begin();
              int v = std::lower_bound(b.begin(), b.end(), i - D) - b.begin();
              if (task < v)
                  ok = false;
              task = std::min(task + mi, u);
          }
          if (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;
 }

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:14:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |       for (int i = 0; i < a.size(); ++i)
      |                       ~~^~~~~~~~~~

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	6724 KB	Output is correct
2	Correct	40 ms	6724 KB	Output is correct
3	Correct	44 ms	6680 KB	Output is correct
4	Correct	39 ms	6664 KB	Output is correct
5	Correct	46 ms	6692 KB	Output is correct
6	Correct	39 ms	6772 KB	Output is correct
7	Correct	39 ms	6696 KB	Output is correct
8	Correct	43 ms	6720 KB	Output is correct
9	Correct	135 ms	6980 KB	Output is correct
10	Correct	136 ms	6928 KB	Output is correct
11	Correct	53 ms	6724 KB	Output is correct
12	Correct	128 ms	13324 KB	Output is correct
13	Correct	233 ms	19908 KB	Output is correct
14	Correct	345 ms	26660 KB	Output is correct
15	Runtime error	386 ms	32952 KB	Memory limit exceeded
16	Runtime error	528 ms	39596 KB	Memory limit exceeded
17	Runtime error	646 ms	46184 KB	Memory limit exceeded
18	Runtime error	722 ms	52792 KB	Memory limit exceeded
19	Runtime error	851 ms	59476 KB	Memory limit exceeded
20	Runtime error	619 ms	46208 KB	Memory limit exceeded